3 ms·

Linked list has a O(N) search time, which is atrocious. A really common optimization is to replace a linear scan on a list with a hash table. In most languages

• ddevault 4y ago
  It's not atrocious unless you need the performance. A linked list with a hundred items which is scanned every 90 seconds or something does not really demand attention for optimization, but it will be simpler, easier to write, easier to understand, and easier to debug, and those are wins are not to be sniffed at. And for the record, Hare does have built-in growable slices, so linked lists are pretty rare in Hare. They exist in a few niche situations -- I only ever wrote a Hare program with linked lists once.
  • BaculumMeumEst 4y ago
    Do you remember what the reason that you went with a linked list in that case? I’ve been learning hare and was curious about where to use them. Also, did you use a nullable pointers to represent the next node element in the linked list? Or a tagged union of ( ptr | void)? Or something else?
    • ddevault 4y ago
      Yep. I used it in a kernel to create a linked list of statically allocated data structures in a context where dynamic allocation was off the table. You can see the code here: https://git.sr.ht/~yerinalexey/carrot/tree/master/item/console/sifive.ha#L100-125 https://git.sr.ht/~yerinalexey/carrot/tree/master/item/conso... Went with nullable pointer types, which is also a rarely used feature in Hare.
      • BaculumMeumEst 4y ago
        Cool, thanks for the link and info
  • ben-schaaf 4y ago
    For sure there's plenty of circumstances where you don't need more performance, but you can't seriously argue re-implementing another linked list is simpler, easier to write, easier to understand or easier to debug than `std::vector`/`Vec`. Multiple allocations and setting up pointers is certainly more complex than allocation/copy. It's most definitely easier to write because you're not writing it, someone else already has. It's easier to read because there's a whole lot less of it. And a single contiguous allocation is way easier to debug.
    • tialaramex 4y ago
      My impression, although it was difficult to be sure, is that Hare's "slices" (or maybe arrays?) are actually vectors, in at least some cases. It seems you can grow them by appending, so they aren't like Rust's slice which is non-owning or a typical array which can't grow. I suspect a Linked List is actually almost never the right shape for a data structure in Hare, because you should just use these vectors to do that. The two actual rationales for Linked List in the 21st century (other than "I was writing C and I don't know what I'm doing") are: 1. Concurrency, Lock Free and sometimes even Wait Free algorithms are practical for Linked List and the other costs pale into comparison on highly contended data structures and 2. I'm doing some serious acrobatics with huge lists, I constantly perform split/ merge operations and so those being cheap is crucial. Hare doesn't have concurrency, and nobody should attempt such acrobatics in a language this dangerous.