29 ms·

Choosing the right data structure isn't in opposition to making simple, readable code; it's part of it. Nothing over-complicates code more than a bad choice of

Choosing the right data structure isn't in opposition to making simple, readable code; it's part of it. Nothing over-complicates code more than a bad choice of data structure. If you pick the data structure that simplifies your code the most, the vast majority of the time that is also the right choice for performance. I disagree with much of the advice in Clean Code, but it has nothing to do with performance. Clean Code is bad because it produces overly-complex unreadable code. The reason that it produces poor performance isn't because the code is too readable; to the contrary, if the code was more readable it would be more obvious that it's using the wrong data structure. I'm not saying that you shouldn't think about performance from the beginning. I'm saying that you shouldn't sacrifice simplicity and readability for the sake of performance until you are sure it's necessary because those things are rarely in opposition to each other on the macro scale. Nothing is worse for performance than doing work you don't need to do and unreadable code tends to do a lot of that if it has been actively maintained for more than a year or two.

josephg 2mo ago
If you go with simple, straightforward data structures you often get adequate performance at the macro level. In my experience, getting really good performance often involves being clever with data structures. It depends how far you want to push performance. I’ve done a lot of work optimising text CRDTs. There, the simple data structure is (essentially) a list which contains metadata for each character. But you’re constantly scanning and inserting into the list. You can improve it in two ways: first, make each list item store the metadata for a connected span of characters. Second, use a b-tree for fast insertion. Make the b-tree store aggregate metadata in internal nodes. That gets you orders of magnitude better performance - O(n) per keystroke to O(log n). RLE gets ~10x lower ram utilisation. It’s only the obvious data structure when you’ve thought about the problem a lot. And you have to write your own btree - there are no libraries for this. At least, none I have found. > I'm saying that you shouldn't sacrifice simplicity and readability for the sake of performance until you are sure it's necessary It really depends on the domain. If you’re making a note taking app, you probably get good enough performance by doing the obvious thing. If you’re making a browser, database, llm inference engine or 3d game engine, it pays to think about perf from the start. But my impression is that most people on this site aren’t doing that sort of thing.
- TheCoelacanth 2mo ago
  That seems like a pretty niche problem. There are already numerous high quality browsers, databases, llm inference engines and 3d game engines and only a tiny portion of devs are working on that type of thing. The vast majority of applications are better off using one of the many high-performance, battle-tested implementations of b-trees that already exist, which, for users of those implementations, is one of the simplest and most commonly used data structures; we just call them databases and filesystems instead of b-trees. Every rule has exceptions but you should know the rules before you decide to break them. For anyone other than an experienced expert, writing your own b-tree implementation in a production system is an extremely foolish decision (if it's for fun or learning, do whatever you want).
  - josephg 2mo ago
    There are already numerous iOS apps and numerous websites. And yet, people keep making more! I think I broadly agree with your overall point. I’ve just spent a lot of my career working on niche problems like this. And there are a lot of people working on systems software. Windows, Linux, macOS, chrome, postgres, etc don’t write themselves. But unless you move in those circles, you can spend your whole life never interacting with any of those engineers. > we just call them databases and filesystems instead of b-trees. The b-trees I’m talking about are in memory. Btrees often outperform other kinds of in memory tree structures (avl, rb, binary, etc) because you get fewer dram memory stalls.
    - TheCoelacanth 2mo ago
      I'm not disagreeing that there are cases where it makes sense to implement a b-tree; I don't think there are any cases where it makes sense to implement a b-tree (in production) as a person who needs beginner-level advice about code organization.

josephg 2mo ago

If you go with simple, straightforward data structures you often get adequate performance at the macro level. In my experience, getting really good performance often involves being clever with data structures. It depends how far you want to push performance. I’ve done a lot of work optimising text CRDTs. There, the simple data structure is (essentially) a list which contains metadata for each character. But you’re constantly scanning and inserting into the list. You can improve it in two ways: first, make each list item store the metadata for a connected span of characters. Second, use a b-tree for fast insertion. Make the b-tree store aggregate metadata in internal nodes. That gets you orders of magnitude better performance - O(n) per keystroke to O(log n). RLE gets ~10x lower ram utilisation. It’s only the obvious data structure when you’ve thought about the problem a lot. And you have to write your own btree - there are no libraries for this. At least, none I have found. > I'm saying that you shouldn't sacrifice simplicity and readability for the sake of performance until you are sure it's necessary It really depends on the domain. If you’re making a note taking app, you probably get good enough performance by doing the obvious thing. If you’re making a browser, database, llm inference engine or 3d game engine, it pays to think about perf from the start. But my impression is that most people on this site aren’t doing that sort of thing.

TheCoelacanth 2mo ago
That seems like a pretty niche problem. There are already numerous high quality browsers, databases, llm inference engines and 3d game engines and only a tiny portion of devs are working on that type of thing. The vast majority of applications are better off using one of the many high-performance, battle-tested implementations of b-trees that already exist, which, for users of those implementations, is one of the simplest and most commonly used data structures; we just call them databases and filesystems instead of b-trees. Every rule has exceptions but you should know the rules before you decide to break them. For anyone other than an experienced expert, writing your own b-tree implementation in a production system is an extremely foolish decision (if it's for fun or learning, do whatever you want).
- josephg 2mo ago
  There are already numerous iOS apps and numerous websites. And yet, people keep making more! I think I broadly agree with your overall point. I’ve just spent a lot of my career working on niche problems like this. And there are a lot of people working on systems software. Windows, Linux, macOS, chrome, postgres, etc don’t write themselves. But unless you move in those circles, you can spend your whole life never interacting with any of those engineers. > we just call them databases and filesystems instead of b-trees. The b-trees I’m talking about are in memory. Btrees often outperform other kinds of in memory tree structures (avl, rb, binary, etc) because you get fewer dram memory stalls.
  - TheCoelacanth 2mo ago
    I'm not disagreeing that there are cases where it makes sense to implement a b-tree; I don't think there are any cases where it makes sense to implement a b-tree (in production) as a person who needs beginner-level advice about code organization.