nicknash

I wonder if you can clear up a memory of mine from IOI 2001. The first day results were delayed, and I seem to remember this is because a contestant encoded the search in one of the problems into a compile time c++ template metaprogram. On the second day, there was then also a compile time limit for solutions, from what I remember. Do you remember any more details of this?

How about this:

What is the most efficient algorithm to generate an N x N array of the integers 0,1,2, … such that each entry is the smallest such integer not appearing either above in the same column, or to the left in the same row?

Posting it in this thread is a bit of a spoiler :)

https://nicknash.me/2012/10/26/happy-halloween/

A fun fact: Each point in the XOR texture is the smallest integer not appearing above it, or to its left

(Ducking while posting my own blog: https://nicknash.me/2012/10/26/happy-halloween/)

Asymptota.com (Sofia/Dubai) | ONSITE

We are a next generation quant trading firm. We aim to be at the leading edge of automation and believe we have an excellent opportunity to challenge more established, larger, less automated incumbents. We are well capitalised, very successful and looking for developers, traders and quants. It’s ok if you want to straddle those roles. We’re especially seeking excellent engineers with good low-level knowledge and deep general software engineering experience. This is a real chance to join a top tier HFT firm and have a huge impact. We think the best work is done in person so relocation to Dubai or Sofia is required. More details: https://www.asymptota.com/open-positions Feel free to drop me a line with any informal questions: nicholas dot nash at asymptota.com Nick

Asymptota.com (Sofia/Dubai) | ONSITE

We are a next generation quant trading firm. We aim to be at the leading edge of automation and believe we have an excellent opportunity to challenge more established, larger, less automated incumbents.

We are well capitalised, very successful and looking for developers, traders and quants. It’s ok if you want to straddle those roles.

We’re especially seeking excellent engineers with good low-level knowledge and deep general software engineering experience.

This is a real chance to join a top tier HFT firm and have a huge impact. We think the best work is done in person so relocation to Dubai or Sofia is required. More details: https://www.asymptota.com/open-positions Feel free to drop me a line with any informal questions: nicholas dot nash at asymptota.com

Nick

Asymptota.com ONSITE (Sofia/Dubai). Remote for truly exceptional candidates. We are a next generation quant trading firm, automating further up the chain than the competition. We are well capitalised, successful and looking for developers, traders and quants.

This is a real chance to join a top tier HFT firm and have a huge impact. More details: https://www.asymptota.com/open-positions Feel free to drop me a line with any informal questions: nicholas dot nash at asymptota.com

Asymptota.com (Sofia/Dubai).

Remote for truly exceptional candidates.

We are a next generation quant trading firm. We automate further up the chain than our competition. We are well capitalised, successful and looking for developers, traders and quants. It’s ok if you want to straddle those roles. We’re still less than 10 people so it’s a real chance to join a top tier HFT firm and have a huge impact. More details: https://www.asymptota.com/open-positions Feel free to drop me a line with any informal questions: nicholas dot nash at asymptota.com

ASYMPTOTA.COM (Dubai, ON-SITE)

Looking for exceptional quant-trader to join our highly successful HFT firm.

You’ll be joining a small, fun, highly collaborative team with deep experience in the most competitive trades on the planet.

Feel free to drop me a line with informal questions, as well as to apply: nicholas.nash@asymptota.com

Asymptota.com (Sofia/Dubai) | Hybrid

We are a next generation quant trading firm. We are well capitalised, successful and looking for developers, traders and quants. It’s ok if you want to straddle those roles. We’re still less than 10 people so it’s a real chance to join a top tier HFT firm and have a huge impact.

We think the best work is done in person so relocation to Dubai or Sofia is required.

More details: https://www.asymptota.com/open-positions Feel free to drop me a line with any informal questions: nicholas dot nash at asymptota.com

Asymptota.com (Sofia/Dubai). Remote for exceptional candidates.

We are a next generation quant trading firm. We are well capitalised, successful and looking for developers, traders and quants.

It’s ok if you want to straddle those roles.

We’re still less than 10 people so it’s a real chance to join a top tier HFT firm and have a huge impact.

More details: https://www.asymptota.com/open-positions Feel free to drop me a line with any informal questions: nicholas dot nash at asymptota.com

Asymptota.com (Sofia/Dubai).

Remote for exceptional candidates.

We are a next generation quant trading firm. We are well capitalised, successful and looking for developers, traders and quants. It’s ok if you want to straddle those roles.

We’re still less than 10 people so it’s a real chance to join a top tier HFT firm and have a huge impact.

More details: https://www.asymptota.com/open-positions

Feel free to drop me a line with any informal questions: nicholas dot nash at asymptota.com

For lock-free data structures, how does this verification encode the memory model? E.g. high-quality model checkers for the C++11 memory model allow for outcomes inconsistent with the execution order of the code (in addition to outcomes that aren't sequentially consistent, but are consistent with the execution order). They also work on unmodified source. In the past I've seen SPIN/Promela used as a tool for concurrency-checking, but it's silent on memory-models (implicitly sequentially consistent)

Sure. I didn't actually mean ssssort. Sometimes it's worth distinguishing between comparison based sorts, and those that make use of key structure, assume a fixed size key universe etc For that reason, I think considering sampling overhead is worth thinking about.

Very cool. In my experience, using a skewed pivot doesn't actually help in practice. Outside of the case you mention (where the input is a random permutation), sampling must be used to choose a skewed pivot, which has a fairly significant overhead.

I think this blog post is also quite a nice write-up of this puzzle, and it includes generalizations:

https://ocfnash.wordpress.com/2009/10/31/yet-another-prisone...

I find this article pretty void of content.

The title is a bit of a give way - to people who work in the space the "Flash Boys" book is easy to see as atrociously inaccurate.

I recommend considering the detailed rebuttal to this type of article, as well as that book in particular: "Flash Boys: Not so Fast" http://www.amazon.com/Flash-Boys-Insiders-Perspective-High-F...

One semi-interesting thing here is that the "killer adversary" described on that page requires knowing that the algorithm you're trying to exploit is quicksort.

Long ago, I wrote adversaries that attempt to force _any_ algorithm that is extracting a partial or total order from data to approach their worst case.

These adversaries, like McIlroy's adversary, sits in the compare() function, but it asks itself "what answer can I give, consistent with the data so far, to force the algorithm to ask me the largest number of subsequent questions?"

For non-introspective quicksorts this will be O(n^2), but it should also bring out the worst constant factors in O(n\logn) worst case time algorithms.

I did some experiments: http://nicknash.me/2012/07/31/adversaries/

A proper reference is the Kahn's "Sorting and Entropy", IIRC.

Interesting that it involved a significant computational effort in verifying the GRH up to a large finite constant.

I think it's right. One way to convince yourself is just to add counters to the implementation of bubble sort, run it for a larger input, and then verify the probabilities (including the conditional probabilities) match what I claim.

You're correct that every permutation of {1, ..., n} is assumed equally likely as an input.

This way of thinking about it might help:

All that "bubble_sweep" does to the input array is to "right-shift" the left-to-right maxima, and "left-shift" the elements between them. The left-shifted elements aren't re-ordered, so they still have the usual probability of being a left-to-right-maxima.

In a bit more detail: Let L be the sequence of indices, from left-to-right, of left-to-right maxima in the array. Now in s^{th} sweep, let M be the sequence L concatenated with n - s. Assume M has r elements in total now.

Then the operation of "bubble_sweep" is just:

a[M_r] <- a[M_{r - 1}] a[M_{r - 1}, ..., M_{r - 2}] <- a[M_{r - 1} + 1, ..., M_r - 1] . . . a[M_2] <- a[M_1] a[M_1, ..., M_2 - 2] <- a[M_1 + 1, .., M_2 - 1]

I think you could actually implement a (very, very) inefficient "bubble_sweep" that worked along these lines. I think that makes it a bit clearer that, apart from at left-to-right maxima from a previous iteration, we just have subsequences of the original (uniform random) permutation, so the 1 - 1/(l+1) probability holds.

I hope that's clear(er) and I didn't make too many mistakes. The sun is shining and I must go ride my bike now!

Agreed. The post wasn't meant to suggest anybody should go and optimize! Just that simple looking code can be tricky/interesting.

Also, even artificially skewing the pivot in quicksort as suggested in the paper you reference doesn't work except on /very/ long pipeline machines, because it worsens cache performance & increases instruction count. Also, even then, it's expensive to randomly sample to generate a skewed pivot (a cost they negelect in that paper, assuming it is free)

Well, all the efficient comparison-based sorting algorithms (i.e. O(n log n) time) will cause Omega(n log n) mispredictions. So in a sense they're all the same*

At the same time, quicksort has the very nice property that if it accidentally picks a somewhat unbalanced pivot it naturally biases its branches making them easier to predict. This essentially cheapens the comparison branches it executes. I don't really know if that helps in practice though.

*Unless you jump through hoops/change the model of computation, one such way being conditional move instructions. There are more impractial ways too. One good way is to use radix sort (it's generally faster for other reasons) and it never compares keys.

Ah no bother -- always a pleasure Paul!

I'm not sure I buy this as a lesson. Choosing between two asymptotically (very) different algorithms (probably linear vs quadratic in your case) isn't really a performance tweak in my book, even though as you point out it wasn't dominant in your case.

Even the world's slowest disk will be faster than a CPU executing a sufficiently silly algorithm.

I'm not sure you're quite right about 1. Depending on what you mean exactly. For example, insertion sort is O(n^2) but mispredicts O(n) times. That doesn't seem often to me.

There are (artificial) mergesorts that execute O(nlogn) branches but also mispredict O(n) times. See for example "branch mispredictions don't affect mergesort:" http://www.cphstl.dk/Paper/Quicksort/sea12.pdf

In the case of 2. I agree, although compiler support still isn't great -- I think. For almost all cases (integers, floats, strings) radix sorting would be even better -- fewer instructions, no comparison branches.

I think you're right about the name! Some people have really thought about its apparent enduring popularity, e.g. Astrachan's old paper:

http://cs.stmarys.ca/~muir/csci4452_11/ClassNotes/Astrachan_...