why is boost lockfree freelist size is limited to a maximum of 65535 objects?

Question

Why is the boost lockfree size is fixed to 65535 objects?

typedef boost::lockfree::queue<int, boost::lockfree::fixed_size<true>> MyQueue;
MyQueue queue(1024*100);

The above code throws exception.

the reasoning i find in the code is that array-based freelists only support a 16bit address space.

what is the reason for this? i am using it on 64bit linux machine. then why limit the addressing to 2**16 items? does the queue use a 'short int' for indexing? does atomic instructions only work for 16bit word size?

what should i do to have a fixed sized queue with more capacity than this?

Fibula

i commented the code in freelist.hpp which throws exception if size is more than 65535, it seems to work fine but i dont see much improvement in performance :( – Fibula

65535 is the maximum size of an unsigned short, maybe it has something to do with that – Fernyak

@IosifM., you are right. i see that there is a class called tagged_index which uses two 16 bit variables. and together this becomes a 32 bit variable which is reintrpreted to be used as an index. and since it uses atomic swap, it uses 32bits for that. But my question still remains why limit it to 16? if make it 32 bits and still atomic instructions can work. – Fibula

This is answered by the lockfree author here: #14893746 – Catton

Answer 1

Boost implementation of lockfree list has to fight the ABA problem. A common workaround is to add extra tag bits to the quantity being considered. Furthermore, Boost has to run on a 32-bit architecture, this means only 32-bit values can be manipulated atomically.

And if we split 32-bit value we can store 16-bit pointers and 16-bit tag. Unsigned 16-bit values are limited to 65535 different values.

Harriman

Thanks @Sergey. if i know i have to use it on 64 bit architecture, how do i modify the source? just change the tagged_index::tag_t and index_t to ba based in unin32_t? – Fibula

Your original questions asks "why" and not "how to fix it". I don't know how to fix it. – Harriman