5 ms·

Most application's bottlenecks are not their linked lists, and optimizing for anything other than your bottleneck is not the wisest use of your time. Performanc

Most application's bottlenecks are not their linked lists, and optimizing for anything other than your bottleneck is not the wisest use of your time. Performance is a budget, and I feel comfortable spending some of that budget on simplicity.

dathinab 4y ago
but maps are simpler to use (if appropriately provided by the language). maps/sets are also fundamentally building blocks for a lot of algorthms and structures, not having them makes it WAY harder to implement them. actually potential impossible as performance can easily degrade to a point where it's unusable when you use O(n) (or worse) lookups instead of O(1) ones. this is not a case of premature optimizations but of missing fundamental building blocks and if you don't want genetics, ok, do it like go did initially make the map special language thingy.
ayende 4y ago
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, that is a trivial step to do, which means that it gets done. There isn't any overhead. With hare, you just blew your complexity budget on this thing.
- 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.
usefulcat 4y ago
Linked lists have generally awful cache locality. If linked lists are not the bottleneck, it's because they already aren't being used for anything where performance matters (which is generally as it should be).

dathinab 4y ago

but maps are simpler to use (if appropriately provided by the language). maps/sets are also fundamentally building blocks for a lot of algorthms and structures, not having them makes it WAY harder to implement them. actually potential impossible as performance can easily degrade to a point where it's unusable when you use O(n) (or worse) lookups instead of O(1) ones. this is not a case of premature optimizations but of missing fundamental building blocks and if you don't want genetics, ok, do it like go did initially make the map special language thingy.

ayende 4y ago

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, that is a trivial step to do, which means that it gets done. There isn't any overhead. With hare, you just blew your complexity budget on this thing.

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.

usefulcat 4y ago

Linked lists have generally awful cache locality. If linked lists are not the bottleneck, it's because they already aren't being used for anything where performance matters (which is generally as it should be).