4 ms·
There's all sorts of application-specific assumptions in this post, that it isn't funny. Ex: Use of hash-tables with insertion ordering to handle a insert-once
by dragontamer 5y ago
There's all sorts of application-specific assumptions in this post, that it isn't funny. Ex: Use of hash-tables with insertion ordering to handle a insert-once task queue (preventing "double tasking" if a task is ever somehow inserted twice?)
Solvable with a Linked-list, circular buffer queue + hash table combined together (hash-table to prevent double-insertions. Linked-list / circular buffer queue for the FIFO functionality).
If O(log(n)) insert/removes are sufficient and you have priorities associated with each element, a Heap data-structure works (all "repeats" will be next to each other, because max-heaps always keep the maximum element on the top)
The goal isn't supposed to be to make a data-structure that magically works in all situations. The goal is to define standard library "components" that can be combined together in ways that matches the performance demands of a particular application.
---------------
And this is all still single-threaded land. If you want a highly performant multithreaded data-structure, you're probably going to have to write your own from scratch (instead of using building blocks from the standard library).
There's just too many performance assumptions that goes into a multithreaded data structure. Is it read-mostly / write-rarely? Read/write balanced? Single-producer / multi-consumer? Multi-producer / single-consumer? Multi-producer / multi-consumer? Is the data-structure able to "count the threads" that may access it and use thread-barriers (thread-pools may practically limit a data-structure to say 64-threads, which means a 64-thread barrier / semaphore can be a highly-performant solution to synchronization) ? Or is it a fully dynamic design where an unbounded number of threads may exist (unbounded number of threads means the sempahore method won't work).
--------
I mean... most people don't care about performance. So a standard library data-structure with a mutex is just fine for well over 95% of applications. But if you care about performance, then suddenly things get complicated.