FastThreadLocal's check with virtual threads improvement

[franz1981]

#15222 has introduced a way to enable virtual threads (which cannot extends FastThreadLocal) to use many FastThredLocalThread optimizations e.g. adaptive unshared magazines, FastThreadLocal::get, etc etc.

This has introduced a binary search vs the thread's id to verify a thread belong to the known set of registered fast thread local threads.
Since loom enable to create many virtual threads which are not fast thread local thread and we can still have a some which are event loops (see https://micronaut.io/2025/06/30/transitioning-to-virtual-threads-using-the-micronaut-loom-carrier/ and https://github.com/franz1981/Netty-VirtualThread-Scheduler) we would like a O(1) way to detect if a virtual thread doesn't belong to this set (ideally, but we need to measure it - which can be tricky!): in https://github.com/franz1981/netty/tree/4.2_not_fasttl_bench I've implemented a microbench which doesn't stress the branch predictor but still stress the log2(event loops) comparisons for such (negative) test.

I was thinking we could implement such in this way (used in openjdk/jdk#18309):

• create an array of (fast thread local) Thread's id ordered based on their hashing value
• store in a long (8 bytes) a bit for each id in the array (hash(id) % 64-th bit position)
• checking for id presence check first the (hash(id) % 64)-th bit: if there's none, it returns immediately
• if the bit is set, count the previous other bits (it's a single ASM instruction) to know the position where to start with searching in the array of ids
• etc etc

This should grant that for decently distributed thread ids and a cheap enough hashing we can have O(1)-ish for both; with slow-path w for loops search (starting from the computed position). Differently from Open addressing with linear probing we cannot just stop searching till the first "empty" is found - since the long id "bloom filter"(ish, again :P ) doesn't allow it (the order of bit set is there to allow the array of ids to be compressed - there are no empty slots, like for hash maps).

wdyt?

[franz1981]

@chrisvest @yawkat FYI

[chrisvest]

With virtual threads, there may be thousands of threads, so I'm not sure about the scalability of this. The current copy-on-write sorted array is also kind of questionable, though. Some kind of hash set that can spread the concurrent accesses and updates would probably be beneficial, I agree.

[franz1981]

@chrisvest I was still expecting the long and arrays of thread ids to be (both in one go) copy-on-write; I forgot to mention it. The registration of thread ids is supposed to be a slow path already

[chrisvest]

@franz1981 maybe, but still feels like we could do better. I wonder if we take something like our LongLongHashMap and make it concurrent, where the key is threadId >>> 6 and the value is a theadId % 64 bit map. I think that could work well for the monotonically increasing thread ids, and a presumably steady peak number of threads (so table expansions are very rare). This would also be a pretty compact representation. Probably smaller than the sorted array of longs.

[yawkat]

I don't see the value in making the thread id set concurrently writable. Where it's useful, it has maybe 8 entries and all of them are set at application startup.

I also want to clarify the "steady peak number of threads" assumption: We can assume a small, fixed number of fake FTL threads, but we cannot assume a fixed number of threads in general, there will be millions or even billions. So a BitSet would not work, but a LongLongHashMap like you describe would.

If that improves the read performance, sure why not. Binary search is not exactly known for being fast.