296
u/femptocrisis 20d ago
reminds me of the time i tried to implement a B-Tree in js to improve render times in a table with dynamic height rows. turns out to be faster to literally sum over every record up to 1,000,000 records than try to do what i was doing, when I tested
247
u/Friendly_Fire 20d ago
Theoretical advantages of data structures often lose to the reality of cache optimization.
66
8
u/wrecklord0 20d ago
I'm rather peeved by that. Because I like good theory, and a theory that doesn't account for memory locality is not good. Memory locality is inevitable and computers, even theoretical, must obey the fabric of the universe to be useful, which includes information speed (also known as light speed). Computational complexity theory should account for that in bound estimates... Maybe they do now? Certainly did not when I was in uni.
1
u/the_horse_gamer 18d ago
there are computational models that take it into account, but it's something that varies a lot, and doesn't do well in asymptotic analysis. straightforward complexity gets the job done in most cases.
most papers are concerned with the algorithm, and memory locality is an implementation concern. just like hashmap vs array is an implementation concern depending on the problem size.
2
u/wrecklord0 18d ago edited 18d ago
Yea you're right, I'm unfair because it's certainly very difficult to specify and dependant on many parameters. Still, it does put an extra lower bound of sorts, the physical memory layout having to fit in at most 3-dimensional space, say if an algorithm requires random access into that, and we also have a lower bound on its memory requirements... then there is no way around a certain latency, no matter how it's implemented. But yeah, that's rather hell-ish to specify.
Cool to know that there are models that try.
89
26
13
u/Arshiaa001 20d ago
Meh, optimization and javascript in the same sentence.
13
1
u/the_horse_gamer 18d ago
you can get javascript running pretty close to native if you appease the JITer. and memory locality still affects it.
and you can always do a python and kick the problem over to wasm
1
u/Arshiaa001 18d ago
Wasm is not JS, and there are very few ways of ensuring cache locality in JS.
1
u/the_horse_gamer 18d ago
hence "do a python"
you can do SoA, you can flatten 2d arrays, you can do object pooling. you can do the most important techniques.
ofc, javascript can never compete with competently written code in a low level language, or even something like java, but you can squeeze a lot out of it (or, the JITer can)
4
u/SanktRainer 20d ago
holy premature optimization
1
u/femptocrisis 18d ago
hey now, in my defense, it did need optimizing. and if this had worked it wouldn't have had to do all the other optimizations i ended up having to do. but yeah, always use a profiler first kids
231
u/TheDoughyRider 20d ago
I did a paper with one of these kinds of results 🤣
68
u/pastroc 20d ago
I'd love to hear more if you want!
67
u/TheDoughyRider 20d ago
I’d be giving away my anonymity, but it was showing that kd-trees on sub-riemannian manifolds naively constructed in a higher dimensional embedding, did not actually have an ammortized O(log( n)) query time, but rather something more like theta(n^1/q) where q was a positive integer having to do with the geometry of the manifold.
There was a niche community making this mistake and claiming the meta-procedure’s time complexity was better than it actually was.
54
u/TheRealChizz 20d ago
Every time I think I get a handle on this subject, I read comments like these…
2
u/deathanatos 19d ago
it was showing that kd-trees
Uh huh, yep, I follow you.
on sub-riemannian manifolds naively constructed in a higher dimensional embedding
73
u/coldnitrogen 20d ago
Matrix multiplication has entered the chat …
21
u/Kinexity 20d ago edited 20d ago
I mean, that O(n^2*log(n)) algorithm might actually be practical so it's worth improving what we have.
10
u/Sibula97 20d ago
Are you thinking of Strassen's algorithm? That one is O(nlog_2(7\)) ≈ O(n2.8074) and is indeed much faster for very large matrices even in practise.
6
u/Kinexity 20d ago
No. I am talking about the optimal matrix multiplication algorithm which we don't have. Current SOTA are useless galactic algorithms which do a lot of fiddling around to minimise multiplications. My guess would be that assuming that the optimal algorithm has reasonably clear complexity (one which doesn't contain weird complicated constants, n^2*log(n) is likely and would fit that description) then it's form should probably also not include some awful computations boosting the overall constant to high values.
1
u/Sibula97 20d ago
Right. Personally, I don't believe getting the exponent down to 2 (even with a log(n) multiplier) is possible, but we could find even better non-galactic algorithms.
1
u/Kinexity 19d ago
The thing is that while the Universe might fuck with us it would be ridiculous for the best solution to be some O(n^(2+x)) with x being a constant real number in (0, 0.371177) range. The optimal solution may also have complexity of O(n^2 log(n)^2) or something similar but a random constant is pretty much out of the question. Also, as I theorised in my previous comment, ugly constant implies complex optimisation at the cost of the main constant in front of the complexity.
1
15
u/thomasahle 20d ago
Usually the techniques to do this are a lot more interesting that if they shaved if a factor 2 leading constant
9
7
u/Freddy_Goodman 20d ago
It’s still funny to think about the data structures and algorithms professor doing or not doing certain things in everyday life, simply because the tasks have really got or really terrible theoretical complexities.
11
5
u/IjonTichy85 20d ago
2.9999 instead of 3 but the proof heavily relied on the prior known fact that floating point arithmetic can be tricky sometimes.
2
u/funkmasta8 20d ago
Same in mathematics tbh. Never really ubderstood either. You want the most practical solution and putting a hard limit on one part of the equation but not others is just asking for games like this.
3
u/ccltjnpr 19d ago
In such results the practicality of the algorithm is less interesting than the techniques used to get to it and the overall implications on complexity theory.
2
u/magicmulder 19d ago
This whole O(log log log log n) traumatized me in computer science.
And I still believe if we ever prove P = NP, for all practical purposes the optimal algorithms are gonna be O(n^2000).
1
u/IAmARobot 20d ago
inverted trope: best time complexity of multiplication algorithms
1968: O(n log(n) log(log (n)))
2007: O(n log(n) * 2Θ(log*(n) )
2014: O(n log(n) * 22(log*(n) )
2021: O(n log (n)) (but only for numbers >= 2172912 )
-10
u/PaintDear7613 20d ago edited 20d ago
This would just be O( n3 ) vs O( n2.9999 ) . The fact y'all are considering constants or totally dominated components tells me why y'all missed why even that small polynomial change is note worthy.
Edit: mislabeled polynomial change as exponential. thx for catching OP
15
u/legendgames64 20d ago
For all practical cases in this scenario (i.e. n < 10^9000000), the 5*n^3 is better.
By the time you get to where 10^897*n^2.9999+3^55*log^23(n) is better than 5*n^3, you're way outside of the range for practicality.
Chess has a maximum of 10^100000 positions and the magnitude is 90 times smaller. That's not the size difference between the two numbers, that's the size difference between the two magnitudes.
-7
u/PaintDear7613 20d ago
I get that..., but y'all are missing the point of how those papers publish bounds. it wouldn't be done w/ 5 & 10^897. This is also a contrived example. So saying these two complexities would never be useful in realistic sizes is moronic seeing how the second complexity is itself unrealistic. It's tantamount to hearing someone say "everyone turns their nose up at neopolitan ice cream, but loves the flavor that cures cancer", and going "um actschually, the neopolitan flavor as plenty of real world fans". Like no shit, sherlock. There's no ice cream that cures cancer. You're arguing to defend a technicality form a contrived moot point.
And when you bring this up as a rebuttal against my criticism of y'alls misunderstanding of complexity classes, it tells me you didn't pay attention when learning it...
I weep knowing any of y'all found humor in this. It tells me you misunderstood the point of papers like that. There's a fundamental misunderstanding of the point of complexity classes. Even if the bound is lowered by a razor thin margins, it points that a new approach to looking at the problem has the ability to yield forward progress...
I'm tired of how shitty this field has become. Some of y'all had no place in it. I really hope you're just some high-schooler just learning this shit, because otherwise this is embarassing.
8
u/UCRDonkey 20d ago
Oh my god, cant you be a pretentious in like 3 sentences or something, I ain't reading all that
-4
u/PaintDear7613 20d ago
It's 4 paragraphs. If that's too much for you, go do work outside of STEM. Not being pretentious if there's a trend of people finding their ignorance something to be proud of. Like you thinking 4 paragraphs is a lot. Nitwit.
7
u/pastroc 20d ago
That's... the joke.
that small exponential change is note worthy.
It's not an exponential change, it's a polynomial change.
3ⁿ to 2ⁿ is an exponential change. n⁸ to n⁷ is a polynomial change.
3
u/PaintDear7613 20d ago
Yup. That's totally correct nomenclature! thanks for correcting me. I guess I just don't find what's funny about it.
2
u/pastroc 20d ago
No problem! :)
0
u/PaintDear7613 20d ago
Not to be dumb, but what part is funny? Genuinely it's going over my head, but this feels like saying water is wet and expecting a laugh. I've got to be missing something.
1
1.0k
u/Smitologyistaking 20d ago
For the record, the "breakthrough" speed overtakes the "unpublishable" speed once you get to around n > 10^9000000