3 ms·

> improving the algorithm or eliminating a SELECT N can make a difference of multiple orders of magnitude Yes and no. The main source of slowness in modern sof

> improving the algorithm or eliminating a SELECT N can make a difference of multiple orders of magnitude Yes and no. The main source of slowness in modern software is memory access (patterns). Yes, a binary search is just O(log(n)) but if your array isn't to big a linear search will probably be faster, just because the chance of your data being in cache is much higher due to prefetching. But it's much harder to plan, program or to refactor software to have a cache friendly memory layout and access pattern. And good luck optimizing your Java, Python, etc. code with respect to memory when even integers are pointers to some data on the heap...

Zababa 4y ago
> The main source of slowness in modern software is memory access I don't think it is. Memory access patterns matters a lot when you want to squeeze every last bit of performance, or when you want to update old code that was optimized for different assumptions. But I think most slowness comes from not having looked at what could make your software slow. Maybe you forgot to compile a regex before a loop, maybe you're copying a whole array at each of the 100 000 iterations, maybe your algorithm is accidentally n^2.
feoren 4y ago
> Yes, a binary search is just O(log(n)) but if your array isn't to big a linear search will probably be faster If your array isn't too big, it's not the bottleneck. You're talking about tippy-top-tier optimizations to eke out the last 10% possible improvement. I'm talking about the extreme prevalence of bad, lazy, thoughtless programming needlessly slowing down most systems by 100x or more. Maybe you work in embedded systems and drop into assembly to manually optimize a hot loop, but most of us don't. Most applications in the world send thousands of SQL queries to a database to do a job that should require only three.

Zababa 4y ago

> The main source of slowness in modern software is memory access I don't think it is. Memory access patterns matters a lot when you want to squeeze every last bit of performance, or when you want to update old code that was optimized for different assumptions. But I think most slowness comes from not having looked at what could make your software slow. Maybe you forgot to compile a regex before a loop, maybe you're copying a whole array at each of the 100 000 iterations, maybe your algorithm is accidentally n^2.

feoren 4y ago

> Yes, a binary search is just O(log(n)) but if your array isn't to big a linear search will probably be faster If your array isn't too big, it's not the bottleneck. You're talking about tippy-top-tier optimizations to eke out the last 10% possible improvement. I'm talking about the extreme prevalence of bad, lazy, thoughtless programming needlessly slowing down most systems by 100x or more. Maybe you work in embedded systems and drop into assembly to manually optimize a hot loop, but most of us don't. Most applications in the world send thousands of SQL queries to a database to do a job that should require only three.