[catlifeonmars]

I appreciate the detailed descriptions and it’s a neat idea, but with respect, this does not strike me as particularly novel. I’d put money down that there are implementations of this in the wild that have been written and forgotten. Kind of analogous to the concept of convergent evolution, this is a natural solution to a particular problem that pops up every once in a while.

[sparkie]

I think it's semi-novel as I have not seen a queue exactly like this, but the structure of the queue itself is not novel - it closely resembles Brodnik et al's RAOTS[1], which also uses an array of pointers to other arrays which increase geometrically in size. RAOTS offer amortized O(1) for most operatons and O(√n) excess space.

Also are Bagwell's VLists[2], which were based on RAOTS, which he presents an example deque for, but this differs from OPs implementation.

A note about the VList versus RAOTS - in Bagwell's paper he claimed the VList performs better, giving a comparison of several soft MSB calculations, which may have been required at the time this was published, but nearly all modern hardware has instructions for very quickly calculating the MSB (Either a singe-cycle instruction, or via count leading zeroes), so it's questionable that there's a real benefit to it as it requires additional metadata which also comes at the cost of power-of-2 alignment of the sub-arrays. However, the VList was designed to be used for a Lisp implementation, for which there may still be other benefits.

    msb = 8*sizeof(size_t) - __builtin_clz(idx)

Or in Java

    msb = Long.SIZE - Long.numberOfLeadingZeroes(idx)

This Multi-Array queue could perhaps benefit from this previous work. In particular, if you constrain the data arrays to be powers of 2 in size, you can use the MSB calculation to very quickly determine the index of the sub-array in the "rings" array, and by masking out the MSB, you determine the index in the sub-array. The RAOTS paper is a forgotten gem which every language developer should be aware of when they're implementing lists in their stdlib. They can be used for immutable lists too in place of linked lists, as cons only requires copying the contents of one sub-array and copying the rings array. In fact, you can modify it slightly to make the rings array a plain old linked-list to make this even cheaper for consing immutable lists, at the cost of slower random-access.

[1]:https://cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf

[2]:https://core.ac.uk/download/pdf/147902641.pdf

[vitpro2213]

Thanks, will look at it.

I actually thought the same: Given e.g. the complex structures published in ACM papers, it would be a surprise if MultiArrayQueue would be a completely new discovery.

We are not in the pioneer years of 1960's anymore (unfortunately :-))

[userbinator]

In particular, embedded stuff (with tight resource constraints) is where you're likely to find this and other "specialised" data structures in use.

[secondcoming]

The embedded space would definitely prefer the ‘fixed size’ problem that this data structure claims to solve.