3 ms·

I mean tbh, a list structure with logN indexed access, insert, and removal seems like a really useful structure. I just wish it was built into languages as on

I mean tbh, a list structure with logN indexed access, insert, and removal seems like a really useful structure. I just wish it was built into languages as one implementation of the list type

usrusr 2y ago
And with predictably good cache locality on iteration. Given the ever increasing gap between the fast and the slow end off our volatile memory hierarchies, I'm surprised that we don't see more of an identifiable trend of using algorithms/structures traditionally associated with spinning disks in nonpersistent memory.
- humzashahid98 2y ago
  B+ Trees (which store data at leaves) rather than B-Trees are what you want for good iteration performance usually. An ordered B-Tree iteration would jump between different arrays in the tree often, but a B+ Tree would only have you jump to another array once you’re done iterating over all the elements in the current array. The following article says the same. https://www.scylladb.com/2021/11/23/the-taming-of-the-b-trees/#:~:text=There%20are%20two%20different%20ways,keys%20from%20its%20left%20subtree https://www.scylladb.com/2021/11/23/the-taming-of-the-b-tree....
SkiFire13 2y ago
FYI this is not that uncommon in functional languages and persistent data structure libraries.
cb321 2y ago
A lot of PLangs have this outside their stdlibs. For example, in Python: https://pypi.org/project/blist/ https://pypi.org/project/blist/ Some C & Nim variants are elsethread (https://news.ycombinator.com/item?id=40441832 https://news.ycombinator.com/item?id=40441832 & https://news.ycombinator.com/user?id=cb321 https://news.ycombinator.com/user?id=cb321 , respectively). -- There seems to be a lot of disagreement about how big stdlibs should be. Personally, I think a large Python one was a selling point (batteries included) as well as the way C++ STL and similar Java ones won over many back in the 1990s. However, in today's modern networked-by-assumption world, stdlib maintainers seem to feel overwhelmed pretty easily and eager to "slough off" as much as they can to the ecosystem. It's likely a sub-discussion of an even more broadly contentious "how narrow/wide should dependency trees" be. What seems to be missing, IMO, are agreed upon "metrics" beyond "saleability of the PL/ecosystem". As guidance for granularity metric relevance, it should be observed that most PL's have some kind of module/separate compilation units. A good answer would be able to work at (and across) many & various levels of the containment hierarchy - at least 3..4 of (procedure, type|module, package, developer, organization). Maybe someone has a set of such metrics in their back pocket, but if so they don't get a lot of exposure in PL chit-chat circles like this one. My guess would be there just isn't enough agreement, but it's probably been fodder for like 100s of software engineering PhD theses. Lol. ( As well as even broader human organization discussions like https://en.wikipedia.org/wiki/Conway's_law https://en.wikipedia.org/wiki/Conway's_law )
- kragen 2y ago
  a relevant fact here is that python was, to a significant extent, guido's attempt to reimplement the abc teaching programming language without the design features that made it useless for anything but programming exercises; one of those, if i recall correctly, was that abc implemented lists as some kind of balanced tree structures (maybe avl trees?), in exactly the way this discussion is about, and was very slow as a result
  - cb321 2y ago
    Just to be clear, I never meant to suggest "only a b-tree", simply the option in the stdlib as per zug_zug (who I did not also take it as suggesting "only"). Different data structures for different use cases as always. JavaScript famously implemented arrays in terms of hash tables and.. In a similar vein, I've also known people who also mistakenly thought B-trees could replace a good hash table as the default &| go-to "associative container", but "order costs" (on one side or another) as you said elsewhere. It's hard to say how much choice needs to be in a stdlib. Hence my exploring how to better say it. :-) E.g., Go has no b-tree in the stdlib, but has a bunch of crypto stuff. Nim has little to no crypto stuff, but has a critbits trie. EDIT: Oh, and FWIW, at least abc-unix used B-trees for list & tables, not AVL trees.
    - kragen 2y ago
      thank you for the correction about abc! b-trees can sometimes replace a general hash table as the default associative array type. in part it depends on programming style and other parts of the language; in lisp, for example, the default associative array type was alists (linked lists of key-value pairs) for a long time, and emacs lisp still uses them pretty extensively. and i think you would be hard-pressed to find an sql implementation for which associative arrays are not usually b-trees—in part because in sql you tend to ask questions like 'which values correspond to these 1000 keys?' more often than 'which value corresponds to this key?', and in part for hysterical raisins. (when they wrote system r, oracle, and ingres, main memory was small, so locality of access was more important than it is now.)
chipdart 2y ago
> I mean tbh, a list structure with logN indexed access, insert, and removal seems like a really useful structure. Indeed B-trees are hardly novel. The point is that no one has a practical need to implement them themselves, unless you're working on rolling out your own database engine. If that's the case then either you're doing that for fun or there were steps in the decision process that I'd love to hear the justification.
- josephg 2y ago
  > I'd love to hear the justification. This is the right data structure to use for collaborative text editing. I made another comment in this thread going in to details. The fastest implementation I know of is Cola, and the author has some great posts going in to details if you’re interested: https://nomad.foo/blog/cola https://nomad.foo/blog/cola
- iamwil 2y ago
  Sometimes, we get paid to hit the high notes, even if we don't sing them all the time, or even every day. See sibling josephg comment on use in CRDT implementation.

I mean tbh, a list structure with logN indexed access, insert, and removal seems like a really useful structure. I just wish it was built into languages as one implementation of the list type

usrusr 2y ago

And with predictably good cache locality on iteration. Given the ever increasing gap between the fast and the slow end off our volatile memory hierarchies, I'm surprised that we don't see more of an identifiable trend of using algorithms/structures traditionally associated with spinning disks in nonpersistent memory.

humzashahid98 2y ago
B+ Trees (which store data at leaves) rather than B-Trees are what you want for good iteration performance usually. An ordered B-Tree iteration would jump between different arrays in the tree often, but a B+ Tree would only have you jump to another array once you’re done iterating over all the elements in the current array. The following article says the same. https://www.scylladb.com/2021/11/23/the-taming-of-the-b-trees/#:~:text=There%20are%20two%20different%20ways,keys%20from%20its%20left%20subtree https://www.scylladb.com/2021/11/23/the-taming-of-the-b-tree....

SkiFire13 2y ago

FYI this is not that uncommon in functional languages and persistent data structure libraries.

cb321 2y ago

A lot of PLangs have this outside their stdlibs. For example, in Python: https://pypi.org/project/blist/ https://pypi.org/project/blist/ Some C & Nim variants are elsethread (https://news.ycombinator.com/item?id=40441832 https://news.ycombinator.com/item?id=40441832 & https://news.ycombinator.com/user?id=cb321 https://news.ycombinator.com/user?id=cb321 , respectively). -- There seems to be a lot of disagreement about how big stdlibs should be. Personally, I think a large Python one was a selling point (batteries included) as well as the way C++ STL and similar Java ones won over many back in the 1990s. However, in today's modern networked-by-assumption world, stdlib maintainers seem to feel overwhelmed pretty easily and eager to "slough off" as much as they can to the ecosystem. It's likely a sub-discussion of an even more broadly contentious "how narrow/wide should dependency trees" be. What seems to be missing, IMO, are agreed upon "metrics" beyond "saleability of the PL/ecosystem". As guidance for granularity metric relevance, it should be observed that most PL's have some kind of module/separate compilation units. A good answer would be able to work at (and across) many & various levels of the containment hierarchy - at least 3..4 of (procedure, type|module, package, developer, organization). Maybe someone has a set of such metrics in their back pocket, but if so they don't get a lot of exposure in PL chit-chat circles like this one. My guess would be there just isn't enough agreement, but it's probably been fodder for like 100s of software engineering PhD theses. Lol. ( As well as even broader human organization discussions like https://en.wikipedia.org/wiki/Conway's_law https://en.wikipedia.org/wiki/Conway's_law )

kragen 2y ago
a relevant fact here is that python was, to a significant extent, guido's attempt to reimplement the abc teaching programming language without the design features that made it useless for anything but programming exercises; one of those, if i recall correctly, was that abc implemented lists as some kind of balanced tree structures (maybe avl trees?), in exactly the way this discussion is about, and was very slow as a result
- cb321 2y ago
  Just to be clear, I never meant to suggest "only a b-tree", simply the option in the stdlib as per zug_zug (who I did not also take it as suggesting "only"). Different data structures for different use cases as always. JavaScript famously implemented arrays in terms of hash tables and.. In a similar vein, I've also known people who also mistakenly thought B-trees could replace a good hash table as the default &| go-to "associative container", but "order costs" (on one side or another) as you said elsewhere. It's hard to say how much choice needs to be in a stdlib. Hence my exploring how to better say it. :-) E.g., Go has no b-tree in the stdlib, but has a bunch of crypto stuff. Nim has little to no crypto stuff, but has a critbits trie. EDIT: Oh, and FWIW, at least abc-unix used B-trees for list & tables, not AVL trees.
  - kragen 2y ago
    thank you for the correction about abc! b-trees can sometimes replace a general hash table as the default associative array type. in part it depends on programming style and other parts of the language; in lisp, for example, the default associative array type was alists (linked lists of key-value pairs) for a long time, and emacs lisp still uses them pretty extensively. and i think you would be hard-pressed to find an sql implementation for which associative arrays are not usually b-trees—in part because in sql you tend to ask questions like 'which values correspond to these 1000 keys?' more often than 'which value corresponds to this key?', and in part for hysterical raisins. (when they wrote system r, oracle, and ingres, main memory was small, so locality of access was more important than it is now.)

chipdart 2y ago

> I mean tbh, a list structure with logN indexed access, insert, and removal seems like a really useful structure. Indeed B-trees are hardly novel. The point is that no one has a practical need to implement them themselves, unless you're working on rolling out your own database engine. If that's the case then either you're doing that for fun or there were steps in the decision process that I'd love to hear the justification.

josephg 2y ago
> I'd love to hear the justification. This is the right data structure to use for collaborative text editing. I made another comment in this thread going in to details. The fastest implementation I know of is Cola, and the author has some great posts going in to details if you’re interested: https://nomad.foo/blog/cola https://nomad.foo/blog/cola
iamwil 2y ago
Sometimes, we get paid to hit the high notes, even if we don't sing them all the time, or even every day. See sibling josephg comment on use in CRDT implementation.