nicknash

The real competitors to a Btree like data structure are trie based structures, such as burst tries, (optimised) q-fast and p-fast tries, level compressed tries, bucketed tries, path compressed tries, etc

Also optimised stratified trees (van emde boas) implementations where key length permits.

Full comparison based structures are rarely necessary: ints, floats, strings, etc can be dealt with by lexicographic structures

Tries in particular work outrageously well on (unrealistic) uniform random data with log-logarithmic operation times

As a result, I’m skeptical of “fastest” here

B trees are great though, good work!

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: [email protected]

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.