6 ms·

Honestly, I think you're setting too high of a bar. If developers learn 2 basic things: 1. How SQL queries work 2. Network latency exists. Moving stuff betwe

Honestly, I think you're setting too high of a bar. If developers learn 2 basic things: 1. How SQL queries work 2. Network latency exists. Moving stuff between your database and your server can get expensive. You'll solve _most_ of the issues that I've seen in my career to this point. There are a few big ones that came from abusing API's too, but it's really the same root issue: You're either thinking about how much information is being moved around or you're not.

lomnakkus 8y ago
> You're either thinking about how much information is being moved around or you're not. Not to put too fine a point on it, but I think you meant how often information is being moved around. That's the scenario where latency has a disproportionate effect on performance. (Bandwidth is usually not a problem these days unless you're doing something at the very high end.)
somenewacc 8y ago
For CPU bound stuff, the 80%/20% rule is to learn that an array/vector is typically much faster than a linked list, and this is due to how CPU caches work. (this is thinking about how much information is being moved around, but between the processor and RAM) Also, for parallel stuff: locks tend to be bottlenecks. Writing parallel code is tricky overall. Stick to libraries that provide high level lockless data structures like mpsc queues if possible.
- adrianN 8y ago
  Who uses linked lists? Outside of niche algorithms that splice lots of lists together there are practically zero occasions where linked lists beat dynamic arrays.
  - deleted 8y ago
    [deleted]
  - hvidgaard 8y ago
    Linked lists are very common, especially for non performance critical code. Dynamic arrays either carry a large performance cost at expansion, or is rather complicated to implement in a amortized way. Linked list in comparison is simple, and since it doesn't require a large continues block of memory, the memory pressure is smaller.
  - Matt3o12_ 8y ago
    A dynamic array has an average (armotized) time of O(1) but a worst case of O(n) – whenever your next insert is longer then the size of the list. Furthermore, it needs a lot of ram whenever copying elements. A linked list is always O(1) and its ram usage is consistent (although not better – normally it is twice or three times as big). A linked list is basically only better on embedded systems because you have much better knowledge about the used ram/runtime. It’s also useful if you have a very large data structure and you need real time performance (a lag of a few hundred milliseconds are unacceptable for some applications such games or financial applications). But whenever your insert becomes too expensive, a linked list is probably not the best choice either and you should consider why your data structure is so big. Lastly a linked list is rather simple to implement but that’s also only really useful for embedded stuff.
  - roel_v 8y ago
    I think it's a cultural thing rather than a technical one. I haven't used a linked list in 15+ years, because in C++ a std::vector is the 'default'. Before that, I wrote (some) C for Gnome, and the 'default' in Glib is a linked list. I don't know/remember if there is a reasonable, easy to use data structure that wraps a dynamically allocated array in Glib, but most of the 'sample' code at the time used the glib list. So that's what everybody kept on doing.
    - pm215 8y ago
      I think GArray is the wrapper for a dynamically allocated array.
      - roel_v 8y ago
        Ah yes it is, thank you. I should have know about this 15 years ago :)
    - blattimwind 8y ago
      I've seen LinkedList often used as the go-to list in Java, instead of ArrayList. They're also common in C, for example, a huge number of structures in the Linux kernel are linked lists.
      - majewsky 8y ago
        > for example, a huge number of structures in the Linux kernel are linked lists. Which allocator is used for these? I'm not familiar with the Linux kernel, but since there is no malloc() in the kernel, I would guess that they allocate from an arena that's going to be page-aligned and thus exhibit the same locality characteristics as a vector.
        blattimwind 8y ago
        Oh, they have malloc, it's just kalled kmalloc.
  - ramchip 8y ago
    Pretty much anyone using a functional language or immutable data structures.
    - Sharlin 8y ago
      The default immutable "list" types in current mainstream functional languages (eg. Scala, Clojure) have much better performance characteristics than naive head:tail linked lists. A typical implementation is a n-ary balanced tree where n is typically on the order of 100, making operations "effectively O(1)" and also keeping cache behavior acceptable in many common cases.
      - twanvl 8y ago
        Haskell still uses head:tail linked lists a lot. However, a lot of effort has been spent in optimizing away the data creation entirely. For example `sum [1..100]` will not actually allocate the list in memory.
  - htgb 8y ago
    What about any time you're working with frequent adds/deletes in arbitrary positions, rather than just at the end of the list? That's not a "niche algorithm" to me, but rather a reasonable use case. The add and delete operations should be faster than for the array case. (Not that I actually use linked list much myself, but I mean I see the use of them.)
    - twanvl 8y ago
      Even then, linked lists are only faster than arrays if the list has at least 100s of items.
      - geezerjay 8y ago
        That's pretty much a standard use case. IIRC the rule of thumb is that if the container isn't expected to hold many elements then the default choice is to use std::vector no questions asked. Otherwise, random insertions and deletions in a sizable container requires a std::list.
    - adrianN 8y ago
      If the list fits in cache it is often to faster to insert into a dynamic array and shift the elements. It of course depends a bit on the allocator that you use how expensive creating a new list node is.
      - htgb 8y ago
        That's a good point, thanks.
  - chrisseaton 8y ago
    > Who uses linked lists? Isn't the linked list pretty much the main collection data structure in the Linux kernel?
  - jawilson2 8y ago
    I use deques A LOT, e.g. interthread messaging, and decaying/windowed time series calculations. Like, if you want a running mean of the last 250ms, you put a timestamp and value pair in the back a deque, and every update you check the front of the deque to see if it should be popped (i.e. the timestamp is older than 250ms), and the mean updated. I suppose you could use a circular buffer with a vector as well, but you have to guess what your max size will ever be, or handle dynamic resizing. Maybe it would be worth it in some circumstances.
    - adrianN 8y ago
      If those lists are anywhere on your hot path benchmarking with a deque build from two vectors, or a circular buffer as you suggested, would be worthwhile imho. The constants in linked lists are such that the O(1) operations are often slower than the O(n) operations in vectors, at least for lists that fit in cache, and depending on your allocator etc. Chasing pointers to more or less random memory locations is pretty much the worst case workload for a modern CPU.
  - deleted 8y ago
    [deleted]
kevin_thibedeau 8y ago
There's more to computing than DB queries over a network.
- labster 8y ago
  Of course there is, but we're talking optimization here and most of the 3% is crappy DB queries.
  - xellisx 8y ago
    Or just the fact there is no caching involved in a lot of cases, so you end up just banging the db so hard it just ends up with 5 minute response times.
    - flukus 8y ago
      IME when people don't know how sql queries work and how network latency works caching tends to just move the problem, not solve it. Instead of n+1 database queries you end up with n+1 cache queries. I deal with this death by a thousand cuts daily at the moment. Every tiny bit of data was being loaded as needed, often from EAV tables. Obviously this sucked or performance so we ended up with an elaborate memory cache that is effectively it's own DBMS which uses a real database as a backing store. This didn't really solve the performance issues though because Hash maps might be fast but they are still far from free and doing 10's of thousands at a time is still quite slow. Fast forward a decade and we have caches in front of caches in front of caches in front of our database instead of just loading courser chunks of data at once.
      - xellisx 8y ago
        The example We had to deal with in the real world was the onslaught of visitors during the American Thanksgiving holiday. The company I worked for would post the ads for Black Friday and Cyber Monday. Yeah, nothing like getting >500K RPS on a 2 DB server setup (Main & Backup) that was highly tuned that would drop to it's knees. The traffic we got, didn't really turn in to that much overall profit, which meant, we couldn't have a huge cluster of DB's to handle the load. Having a caching system using Memcached (120 second query cache), we were able to handle that load like it was nothing. We used caching on other parts of the system, but the DB cache is what saved us from having to leave the dinner table every 15 minutes.
mpweiher 8y ago
3. When [not] to use a database. 4. When [not] to use the network A lot of the performance wins I have been able to pull off (1000x) were from removing unnecessary distribution and unnecessary databases.
- Reedx 8y ago
  I'm curious (maybe some lessons or good horror stories there), what are people using databases for that they shouldn't?
  - skolsuper 8y ago
    $current_product has a table with 3 rows that is used for config. Every other table has a foreign key to this one. It was designed as a multi-tenant application that never got over 3 tenants. Other tables are over 1billion rows already. The 3-row table is mostly json columns, and is basically untouchable now.

lomnakkus 8y ago

> You're either thinking about how much information is being moved around or you're not. Not to put too fine a point on it, but I think you meant how often information is being moved around. That's the scenario where latency has a disproportionate effect on performance. (Bandwidth is usually not a problem these days unless you're doing something at the very high end.)

somenewacc 8y ago

For CPU bound stuff, the 80%/20% rule is to learn that an array/vector is typically much faster than a linked list, and this is due to how CPU caches work. (this is thinking about how much information is being moved around, but between the processor and RAM) Also, for parallel stuff: locks tend to be bottlenecks. Writing parallel code is tricky overall. Stick to libraries that provide high level lockless data structures like mpsc queues if possible.

adrianN 8y ago
Who uses linked lists? Outside of niche algorithms that splice lots of lists together there are practically zero occasions where linked lists beat dynamic arrays.
- deleted 8y ago
  [deleted]
- hvidgaard 8y ago
  Linked lists are very common, especially for non performance critical code. Dynamic arrays either carry a large performance cost at expansion, or is rather complicated to implement in a amortized way. Linked list in comparison is simple, and since it doesn't require a large continues block of memory, the memory pressure is smaller.
- Matt3o12_ 8y ago
  A dynamic array has an average (armotized) time of O(1) but a worst case of O(n) – whenever your next insert is longer then the size of the list. Furthermore, it needs a lot of ram whenever copying elements. A linked list is always O(1) and its ram usage is consistent (although not better – normally it is twice or three times as big). A linked list is basically only better on embedded systems because you have much better knowledge about the used ram/runtime. It’s also useful if you have a very large data structure and you need real time performance (a lag of a few hundred milliseconds are unacceptable for some applications such games or financial applications). But whenever your insert becomes too expensive, a linked list is probably not the best choice either and you should consider why your data structure is so big. Lastly a linked list is rather simple to implement but that’s also only really useful for embedded stuff.
- roel_v 8y ago
  I think it's a cultural thing rather than a technical one. I haven't used a linked list in 15+ years, because in C++ a std::vector is the 'default'. Before that, I wrote (some) C for Gnome, and the 'default' in Glib is a linked list. I don't know/remember if there is a reasonable, easy to use data structure that wraps a dynamically allocated array in Glib, but most of the 'sample' code at the time used the glib list. So that's what everybody kept on doing.
  - pm215 8y ago
    I think GArray is the wrapper for a dynamically allocated array.
    - roel_v 8y ago
      Ah yes it is, thank you. I should have know about this 15 years ago :)
  - blattimwind 8y ago
    I've seen LinkedList often used as the go-to list in Java, instead of ArrayList. They're also common in C, for example, a huge number of structures in the Linux kernel are linked lists.
    - majewsky 8y ago
      > for example, a huge number of structures in the Linux kernel are linked lists. Which allocator is used for these? I'm not familiar with the Linux kernel, but since there is no malloc() in the kernel, I would guess that they allocate from an arena that's going to be page-aligned and thus exhibit the same locality characteristics as a vector.
      - blattimwind 8y ago
        Oh, they have malloc, it's just kalled kmalloc.
- ramchip 8y ago
  Pretty much anyone using a functional language or immutable data structures.
  - Sharlin 8y ago
    The default immutable "list" types in current mainstream functional languages (eg. Scala, Clojure) have much better performance characteristics than naive head:tail linked lists. A typical implementation is a n-ary balanced tree where n is typically on the order of 100, making operations "effectively O(1)" and also keeping cache behavior acceptable in many common cases.
    - twanvl 8y ago
      Haskell still uses head:tail linked lists a lot. However, a lot of effort has been spent in optimizing away the data creation entirely. For example `sum [1..100]` will not actually allocate the list in memory.
- htgb 8y ago
  What about any time you're working with frequent adds/deletes in arbitrary positions, rather than just at the end of the list? That's not a "niche algorithm" to me, but rather a reasonable use case. The add and delete operations should be faster than for the array case. (Not that I actually use linked list much myself, but I mean I see the use of them.)
  - twanvl 8y ago
    Even then, linked lists are only faster than arrays if the list has at least 100s of items.
    - geezerjay 8y ago
      That's pretty much a standard use case. IIRC the rule of thumb is that if the container isn't expected to hold many elements then the default choice is to use std::vector no questions asked. Otherwise, random insertions and deletions in a sizable container requires a std::list.
  - adrianN 8y ago
    If the list fits in cache it is often to faster to insert into a dynamic array and shift the elements. It of course depends a bit on the allocator that you use how expensive creating a new list node is.
    - htgb 8y ago
      That's a good point, thanks.
- chrisseaton 8y ago
  > Who uses linked lists? Isn't the linked list pretty much the main collection data structure in the Linux kernel?
- jawilson2 8y ago
  I use deques A LOT, e.g. interthread messaging, and decaying/windowed time series calculations. Like, if you want a running mean of the last 250ms, you put a timestamp and value pair in the back a deque, and every update you check the front of the deque to see if it should be popped (i.e. the timestamp is older than 250ms), and the mean updated. I suppose you could use a circular buffer with a vector as well, but you have to guess what your max size will ever be, or handle dynamic resizing. Maybe it would be worth it in some circumstances.
  - adrianN 8y ago
    If those lists are anywhere on your hot path benchmarking with a deque build from two vectors, or a circular buffer as you suggested, would be worthwhile imho. The constants in linked lists are such that the O(1) operations are often slower than the O(n) operations in vectors, at least for lists that fit in cache, and depending on your allocator etc. Chasing pointers to more or less random memory locations is pretty much the worst case workload for a modern CPU.
- deleted 8y ago
  [deleted]

kevin_thibedeau 8y ago

There's more to computing than DB queries over a network.

labster 8y ago
Of course there is, but we're talking optimization here and most of the 3% is crappy DB queries.
- xellisx 8y ago
  Or just the fact there is no caching involved in a lot of cases, so you end up just banging the db so hard it just ends up with 5 minute response times.
  - flukus 8y ago
    IME when people don't know how sql queries work and how network latency works caching tends to just move the problem, not solve it. Instead of n+1 database queries you end up with n+1 cache queries. I deal with this death by a thousand cuts daily at the moment. Every tiny bit of data was being loaded as needed, often from EAV tables. Obviously this sucked or performance so we ended up with an elaborate memory cache that is effectively it's own DBMS which uses a real database as a backing store. This didn't really solve the performance issues though because Hash maps might be fast but they are still far from free and doing 10's of thousands at a time is still quite slow. Fast forward a decade and we have caches in front of caches in front of caches in front of our database instead of just loading courser chunks of data at once.
    - xellisx 8y ago
      The example We had to deal with in the real world was the onslaught of visitors during the American Thanksgiving holiday. The company I worked for would post the ads for Black Friday and Cyber Monday. Yeah, nothing like getting >500K RPS on a 2 DB server setup (Main & Backup) that was highly tuned that would drop to it's knees. The traffic we got, didn't really turn in to that much overall profit, which meant, we couldn't have a huge cluster of DB's to handle the load. Having a caching system using Memcached (120 second query cache), we were able to handle that load like it was nothing. We used caching on other parts of the system, but the DB cache is what saved us from having to leave the dinner table every 15 minutes.

mpweiher 8y ago

3. When [not] to use a database. 4. When [not] to use the network A lot of the performance wins I have been able to pull off (1000x) were from removing unnecessary distribution and unnecessary databases.

Reedx 8y ago
I'm curious (maybe some lessons or good horror stories there), what are people using databases for that they shouldn't?
- skolsuper 8y ago
  $current_product has a table with 3 rows that is used for config. Every other table has a foreign key to this one. It was designed as a multi-tenant application that never got over 3 tenants. Other tables are over 1billion rows already. The 3-row table is mostly json columns, and is basically untouchable now.