Re:Factor is faster than Zig
by otabdeveloper4 on Saturday November 11, 2023 @04:47AM
(#38228843)
Linked lists are necessary when you have structures that can't be moved. Very important in a highly concurrent or lockfree environment.
How could you use the Rust standard library's linked list for that?
Can't you have a list of pointers instead?
Resizing/deleting items in list in most implementations are either not lock free or not threadsafe
Yeah, but what if you just use smaller lists and point to the next/previous list?
Hold on...
Linked lists aren't either so....?
A deque will usually work just as well in that environment and it will always have better general performance characteristics. There are very few legitimate uses of linked lists.
Re:Factor is faster than Zig
by otabdeveloper4 on Saturday November 11, 2023 @01:25PM
(#38233000)
A deque is a doubly-linked list under the hood.
Re:Factor is faster than Zig
by adgjlsfhk1 on Saturday November 11, 2023 @08:22PM
(#38236344)
Array based deques are very common (and usually much faster). Doubly linked lists are absolutely awful for memory locality.
This reminds me of Aria's comment in her Rust tutorial https://rust-unofficial.github.io/too-many-lists/ about failing to kill LinkedList. One philosophy (and the one Rust chose) for a stdlib is that this is only where things should live when they're so commonly needed that essentially everybody needs them either directly or to talk about. So, HashTable is needed by so much otherwise unrelated software that qualifies, BloomFilter, while it's real useful for some people, not so much. Aria cleaned out Rust's set of standard library containers before Rust 1.0, trying to keep only those most people would need. LinkedList isn't a good general purpose data structure, but, it was too popular and Aria was not able to remove it.
Having multiple hash tables feels like a win (they're optimized for different purposes) but may cost too much in terms of the necessary testing to ensure they all hit the quality you want.