They’re too ridiculous… unless a more optimal solution does not exist

Skiena has a great table in his algorithms book mapping time complexity to hypothetical times for different input sizes.

For n of 10^9, where lgn takes 0.03 us and n takes 1 s, nlgn takes 29.9 s and n^2 takes 31.7 years.

To be clear though, that isn't his second law, at least as of two months ago, according to https://bsky.app/profile/randomascii.bsky.social/post/3lk4c6...

  | n   | n log n  |
  | 5   | 8.0472   |
  | 10  | 23.0259  |
  | 25  | 80.4719  |
  | 50  | 195.6012 |
  | 100 | 460.5170 |

But sometimes a big enough C can flip which solution helps you hit your margins.

I was just helping out with the network at an event. Worked great in testing, but it failed in production due to unicast flooding the network core. Turns out that some of the PoE Ethernet switches had an insufficiently sized CAM for the deployment combined with STP topology changes reducing the effective size of the CAM by a factor of 10 on the larger switches. Gotta love when packet forwarding goes from O(1) to O(n) and O(n^2)! Debugging that in production is non-trivial as the needle is in such a large haystack of packets so as to be nearly impossible to find in the output of tcpdump and wireshark. The horror... The horror...

Pick any compiled language and test it. Pick an algorithm making heavy use of a small (<10, maybe up to a hundred elements) hashset, and try using a linear structure instead. The difference will be most apparent with complicated keys, but even strings of more than a few characters should work.

Some example workloads include:

1. Tokenization (checking if a word is a keyword)

2. Interpretation (mapping an instruction name to its action)

3. ML (encoding low-cardinality string features in something like catboost)

4. JSON parsers (usually key count is low, so parse into a linear-scan hashmap rather than a general-purpose hashmap)

Details vary in the exact workload, the hardware you're using, what other instructions you're mixing in, etc. It's a well-known phenomenon though, and when you're doing a microoptimization pass it's definitely something to consider. 2x speedups are common. 10x or more happen from time to time.

It's similar to (but not _quite_ the same as) the reason real-world binary search uses linear scans for small element counts.

When you go to really optimize the system, you'll also find that the linear scan solution is often more amenable to performance improvements from batching.

As to how much it matters for your composite program? Even at a microoptimization level I think it's much more important to pay attention to memory access patterns. When we wrote our protobuf parser that's all we really had to care about to improve performance (33% less execution time for the entire workload, proto parsing being much better than that). You're much more likely to be able to write sane code that way (contrasted with focusing on instructions and whatnot first), and it's easier to layer CPU improvements on top of a good memory access pattern than to go the other way around.

    > That is not the case in C though, as it is much easier to use arrays and nested loops instead of hash maps.

I am confused. There are plenty of open source, fast hash map impls in C.

> Real production use cases don't have small 'n'.

Real production use cases absolutely have small n. You don't hear about them, because it's very hard for them to cause issues. Unless the use case changes and now the n is not small anymore and nobody noticed the trap.

I have an app that's been running an O n^2 algorithm in "production" (free open source app used by various communities) for about half a year now.

It's been fine because "n" is "number of aircraft flying in this flight simulator" - and the simulator's engine starts to fail above around 2000 anyway. So even in the worst case it's still going to run within milliseconds.

Or, phrased differently, if n has an upper limit, the algorithm is O(1).

I think that's why they specified the "BTRFS snapshots" part. Yes, directly syncing a .git directory seems like a recipe for disaster with how often I've seen individual files lagging to sync, but I guess with BTRFS snaphots one can ensure that only a consistent view of a git directory is being backed up and synced.

I think GP's point is that the filesystems used by someone self-hosting gitlab may not be the same as what gitlab themselves are using.

File systems can be weird. Sometimes the OS can be weird and fsync type calls may not do what you expect. At least at one point MacOS fsync didn't behave the same way as Linux (i.e. Linux should ensure the write is truly done and not just in cache so long as the drive isn't lying). [0]

> There are system requirements that a customer would be expected to adhere to if they wanted a valid enterprise support contract with one of these vendors.

Gitlab has a community edition. Not handling data well would be bad for their public image.

[0] - https://news.ycombinator.com/item?id=30372218

I can't reply to the other reply for some reason, but what they said is indeed what I meant. gitlab.com might be running their Gitaly servers on btrfs or zfs or lvm volumes or whatever, but other customers may be using ext2. Gitlab the company could require customers to only run Gitaly on a specific filesystem, but up to now, they never have, it would be pretty shitty to suddenly change their minds after a decade plus of establishing one expectation, and whoever the developer is who submitted the patch to upstream Git and got a technical blog post out of it has absolutely no power to dictate contract terms to enterprise customers personally and instead did what is actually in their power to do.

You should if you expect your readers to be normal humans who understand obvious context, and not pedantic HN readers who understand obvious context but delight in nit-picking it anyway.

I somewhat agree, but for lack of a better word, what would you use? Quadratically doesn't have the same punch

I find the whole article rather poorly written. Most likely using an LLM.

“Words mean things.”

If you can’t agree with this, then you shouldn’t be speaking or writing, IMO.

Those who argue that words that mean different things are actually equivalent have no business dealing with language.

But if you happen to have n=2^c, then an algorithm with logarithmic complexity only needs c time. Thats why this is usually referred to as exponential speedup in complexity theory, just like from O(2^n) to O(n). More concretely if the first algorithm needs 1024 seconds, the second one will need only 10 seconds in both cases, so I think it makes sense.

It depends if you consider "speedup" to mean dividing the runtime or applying a function to the runtime.

I.e. you are saying and f(n) speedup means T(n)/f(n), but others would say it means f(T(n)) or some variation of that.

Exponentially bad word choice even... since we're using that word however we want now?

I don't think this is meaningless or non-constructive pedantry - we're a technical community and those are technical words.

Sloppy writing is up orders of magnitude lately.

My personal pet peeve is when the term “exponentially” is used to refer to a change between precisely two data points.

It’s a very specific subset of the one you’re describing.

“Tell me you don’t know what you’re talking about without telling me you don’t know what you’re talking about.”

So long as you have an existing CI/CD story, or are willing to invest in head-to-heading them, to find one that fits your needs. Because both it and Forgejo's "we're deploying act, what could go wrong" give me the heebie-jeebies. And, aside from that, there are so many FLOSS ones they could have chosen that legitimately work making that decision extra opaque to me

Which term is appropriate here? What would you suggest? (honest question)

Art term?

Why are you making a new account for each comment? You seem to be deliberately avoiding HN's moderation system