News for hackers. Stuff that matters.
Re:When Big O Fools You by qwertyuiop924 on Tuesday August 23, 2016 @01:46PM (#12345710)
Here's a question: How often does this matter? No, not that big O can fool you. That always matters.

How often does it matter that non-contigouous memory access is slow? Really. How much do those few useconds really matter? In most apps, I would guess that a CPU cache miss isn't noticable by humans.

Yes, non-contiguous structures are significantly slower, but if you don't need to be as fast as possible, eliminating them for that reason only (assuming that there is any non-perf reason to stick with them) is a premature optimization.

But if you ARE optimizing, yeah, you need to think about how often worst-case occurs. Because big O only tells you about worst-case. NOT the average.

Re:When Big O Fools You by corysama on Tuesday August 23, 2016 @02:32PM (#12346216)
A cache miss isn't noticeable by a human. Code that cache misses a lot runs 10-100x slower than code that takes into consideration that it's running on a physical machine and not an abstraction. That is very noticeable by humans. Even when your data structures and algos are designed with a nice O(logN), it's very noticeable when one program bogs down with 1/6 the data compared to another.

I work in games, so the story I tell new kids is: The PlayStation2 ran at 300Mhz and a cache miss would cost you 50 cycles. The PlayStation3 ran at 3200Mhz and a cache miss would cost you 500 cycles. So, if you are cache missing a lot, your PS3 game will run as if it were on a PS2.

In other words, not paying attention to cache make your computer run like it's 10 years older than it is. You paid for a modern machine, but you are getting the results of a Craigslist junker. This is true outside of games. It's the reason 4x2Ghz cellphones struggle to run seemingly simple apps. It's a big part of the reason people struggle to orchestrate armies of servers (distributed computing is easier when it's 90% less distributed).

Is it really harder to work with the cache system instead of ignoring it? Yeah, it requires a tiny bit of study an a little bit of planning. In contrast, the theme I see a lot online is to completely dismiss physical reality in favor or theory. And, the theme I see almost universally in the students (and many senior engineers) I interview is complete ignorance of the very existence of cache and it's effects on the code they write. It's very concerning...

Re:When Big O Fools You by qwertyuiop924 on Tuesday August 23, 2016 @03:46PM (#12346871)
No, I don't deny it's important to know that cache misses exist, and what they can do: to the contrary, it's vital.

However, in 90% of applications, it's not going to matter, because those applications are spending hundreds of cycles waiting anyways: Disk or network IO, user input, all that stuff is way slower than a cache miss. If you're writing a video game, or a database, or other software with very high soft-realtime speed requirements, or heavy data access, by all means, optimize to avoid cache miss.

But if you're writing a company-internal Rails app, nobody's going to notice, even if you're getting cache miss after cache miss. Which you probably won't.

Actually, if your language isn't compiled, a cache miss is the least of your worries, perf-wise.

And now I've got to see if I can optimize my code to avoid cache misses. But the code's in Scheme, so unless the initial access cost is amortized, I'm already doomed...

Re:When Big O Fools You by Koromix on Tuesday August 23, 2016 @04:36PM (#12347357)
You're looking at this problem backward. For example, you mention user input. Users may need a second to click or touch a button, but when they do the software should react instantly, and that does not leave you that many cycles. My smartphone's lock screen is my go-to example: most times it fails to follow my finger, and I barely have anything running on it.

Most of the dynamic languages are data and instruction cache-miss machines. They chase objects and pointers all around the memory.

Re:When Big O Fools You by qwertyuiop924 on Tuesday August 23, 2016 @05:13PM (#12347695)
>My smartphone's lock screen is my go-to example: most times it fails to follow my finger, and I barely have anything running on it.

...That doesn't sound like a cache miss. Knowing Android, A cache miss is probably the least of your worries.

>Users may need a second to click or touch a button, but when they do the software should react instantly, and that does not leave you that many cycles.

You raise a good point...

>Most of the dynamic languages are data and instruction cache-miss machines. They chase objects and pointers all around the memory.

...and this is part of my point. If you look at a problem and think, "A high-level language is fast enough," then you are implicitly saying that the latency of a cache miss is acceptable. And IME, in most cases that's true. I mean, heck, I'm using Scheme, so while I may have pointer chases like the Amazon has trees, but I CAN optimize them into array lookups, and my code is compiled: not great, but better than most HLLs.

It's the same argument as always: perf vs. development speed. You can be in the C and FP loop, or the Lisp and JS loop.

Re:When Big O Fools You by Koromix on Tuesday August 23, 2016 @06:00PM (#12348102)
> That doesn't sound like a cache miss. Knowing Android, A cache miss is probably the least of your worries.

My example was meant to illustrate the user input problem. From what I know about Android, the absymal performance is very much a case of "death from a thousand cuts".

> It's the same argument as always: perf vs. development speed. You can be in the C and FP loop, or the Lisp and JS loop.

The fast(er) languages we have are old and full of warts, and that makes them slow to develop in. The heavily used HLLs such as Python and Ruby were made by people who did not care much (at all?) about performance, and it shows in many design decisions. But here's the thing: we could have both at the same time. I don't buy this dichotomy.

Re:When Big O Fools You by qwertyuiop924 on Tuesday August 23, 2016 @08:32PM (#12348869)
>But here's the thing: we could have both at the same time. I don't buy this dichotomy.

That's actually not true: OO, dynamism, late binding, and a lot of the other things that HLLs have to offer require a lot of pointer chasing and non-consecutive datastructures. I'm mostly a Schemer, and Scheme and Lisp have had decades of research put into making them compile and run fast. Most dynamic languages aren't so lucky. But the required pointer chasing and garbage collection mean they'll never be as fast as C.

Functional programming languages, however, are rarely late-binding, and don't expose as much about their implementation, so some of the pointer chasing can be avoided.

Rust doesn't need a GC, and is fairly C-like - or rather, ALGOL-like and BLISS-like - with added memory safety. So with a programmer who knows what they're doing, it can be pretty fast. But here's the rub: the faster a language is, the closer it has to be to the metal, and the less it can do with high-level features.

So yes, you can make HLLs faster, but you can't take the cache misses out of an HLL, and you can't make a systems language wearing an HLL's clothing - although Rust is making an admirable attempt.

Re:When Big O Fools You by Koromix on Wednesday August 24, 2016 @12:38AM (#12349712)
> OO, dynamism, late binding

None of these are required for ease of development. At least the first two often result in precisely the opposite.

HLLs are not required to focus on slow abstractions. For example, homogeneous arrays of tagged unions can replace inheritance most of the time. And they avoid breaking your code in 10 files and 20 classes (though for some reason this metric is seen as a good thing way too often).

Re:When Big O Fools You by qwertyuiop924 on Wednesday August 24, 2016 @02:32AM (#12350137)
OO, perhaps, but without dynamism and late binding, metaprogramming is difficult, as is any number of techniques. Like, for instance, class generation, and extending methods.

And while I don't set much store by inheritance, it set considerably more store by duck-typing and polymorphism.

>None of these are required for ease of development. At least the first two often result in precisely the opposite.

So are you talking about Java-style OO? Because I was talking about Smalltalk OO, which is pretty different.

Required, no, but they're tools, and they come in handy. Certainly make development a lot more comfortable.

And some of the time, they make delvelopment a lot easier.

Re:When Big O Fools You by Koromix on Wednesday August 24, 2016 @08:10AM (#12351403)
> Like, for instance, class generation, and extending methods.

This is precisely the kind of thing that leads to unmaintainable "magic" code, even though it can still be useful but with extreme moderation. So I don't see the point of making that a core feature of any language.

If you have any example to the contrary, I'd love a link to a good open-source project that uses these things extensively.

Re:When Big O Fools You by qwertyuiop924 on Wednesday August 24, 2016 @08:41AM (#12351559)
RSpec? A lot of ruby uses metaprogramming in some respect.

As for not seeing the point of making it a feature of your language, how about Lisp? And I'm not just talking macros. Lambdas, late binding, and in Scheme, the ability to rebind anything lead to a lot of cool tricks and capabilities.

And late binding is extrordinarily important.!

Re:When Big O Fools You by Koromix on Wednesday August 24, 2016 @10:24AM (#12352223)
I don't consider the Ruby ecosystem to be a good example of much. Idiomatic Ruby code is much slower and usually not more maintainable than C++. Actually, it may even be worse thanks to dynamic typing, which makes refactoring much more painful than it already is in large code bases.

Well I guess it's good at making CRUD web sites. Hardly rocket science.

Re:When Big O Fools You by qwertyuiop924 on Wednesday August 24, 2016 @11:23AM (#12352688)
Okay then: Lisp.

Tinyclos is a fairly sophisticated implementation of OO and the MOP, written in Scheme.

Its descendants, COOPS, GOOPS, and others, are in most schemes today. Many of them are written in their respective dialect of scheme, with little or no specific compiler support.

SXML allows for writing XML in native scheme syntax.

The anaphoric macros (aif, acond, etc.) are all, well, macros, and thus use metaprogramming principles.

tclOO, [incr tcl], and other OO TCL systems are usually implemented in regular TCL.

Give or take, any large Lisp or Smalltalk codebase takes advantage of dynamic typing, late binding, and some form of metaprogramming.

However, you've made it clear that you hate Ruby, Dynamic Typing, and other such things, as given as much of metaprogramming requires this sort of flexibility, I very much doubt anything I say will convince you that dynamic languages are in any way useful.

Re:When Big O Fools You by Koromix on Wednesday August 24, 2016 @12:19PM (#12353117)
I don't hate them. I've used python more than once, and will continue to do so. And I think it's great teaching material. It's a good scripting language. But I think its drawbacks far outweigh its advantages for large projects.

All your examples are programming gimmicks, and I've yet to see stuff that solves actual hard problems. I'm not interested in programming for programming's sake. I want to use it to make my computer do useful stuff.

Re:When Big O Fools You by qwertyuiop924 on Wednesday August 24, 2016 @01:23PM (#12353618)
Gimmicks? Some of them, yes, but CLOS and its descendants are used in Real applications, as are the TCL OO systems. But if you want Real World, I'll give you real world.

Maxima is a descendant of the original MACSYMA, developed at MIT. It is still a usable and viable system, even if it has ageda bit.

Emacs is a popular programmer's text editor written in C and a dialect of lisp.

Both of the above programs are large, useful, and written in an HLL - one particularly amenable to pointer chasing, I might add - and they make use of the variety of abstractions which that HLL provides.

If those aren't modern enough for you, check out some Clojure applications.

Re:When Big O Fools You by yxhuvud on Tuesday August 23, 2016 @04:35PM (#12347341)
Considering the Ruby object and memory models, you probably will get cache miss after cache miss. You just won't have the tools to do anything about them.
Re:When Big O Fools You by qwertyuiop924 on Tuesday August 23, 2016 @05:05PM (#12347633)
You're probably right. I was just thinking, "It can't possibly be THAT bad," especially seeing as there are so many objects that are referenced frequently.
Re:When Big O Fools You by malisper on Tuesday August 23, 2016 @03:05PM (#12346522)
This advice applies a ton to databases. At my job, our application is heavily disk i/o bound, with a database query typically taking several seconds. I benchmarked how different sorting the rows in our db by time would be compared to our current layout (partially sorted by user, partially sorted by time, which was completely accidental). Sorting by time benchmarked ~10x faster, which is absolutely huge.
Re:When Big O Fools You by qwertyuiop924 on Tuesday August 23, 2016 @03:50PM (#12346915)
Yeah, heavy data access is where this matters.
Re:When Big O Fools You by timmytokyo on Tuesday August 23, 2016 @02:15PM (#12346026)
In game dev, it often matters a lot. The difference between code that takes cache performance into account and code that does not is often measured in frames per second.
Re:When Big O Fools You by cdavid on Tuesday August 23, 2016 @01:51PM (#12345768)
Memory contiguity may be the most fundamental thing to keep in mind when doing numerical computing, for example.
Re:When Big O Fools You by qwertyuiop924 on Tuesday August 23, 2016 @03:48PM (#12346894)
Okay, so now I know.
Re:When Big O Fools You by omgtehlion on Tuesday August 23, 2016 @04:10PM (#12347123)
> How much do those few useconds really matter

There is at least one area where even a split micro will cost you millions.

P.S.: and even in consumer apps there microseconds here and there add up and then user will have overall sluggish experience.

Re:When Big O Fools You by SamReidHughes on Tuesday August 23, 2016 @02:10PM (#12345982)
Big O notation is used to describe whatever you want it to. The average case is the usual choice, in fact.
Re:When Big O Fools You by qwertyuiop924 on Tuesday August 23, 2016 @03:28PM (#12346732)
Oh. Sorry.
Re:When Big O Fools You by pmelendez on Tuesday August 23, 2016 @03:13PM (#12346598)
In games, critical systems and high traffic backend systems it means a lot.
Re:When Big O Fools You by qwertyuiop924 on Tuesday August 23, 2016 @03:48PM (#12346889)
That I could guess. My point is that most code isn't in high traffic backend systems and games.
Re:When Big O Fools You by TillE on Tuesday August 23, 2016 @04:16PM (#12347184)
There are a million things that a person writing a boring CRUD web app doesn't need to know. But if you want to be a good programmer, you should probably understand how a computer works.
Re:When Big O Fools You by qwertyuiop924 on Tuesday August 23, 2016 @05:24PM (#12347807)
I didn't say you shouldn't. I just asked how often that kind of performance optimization mattered. The world is not comprised only of CRUD and situations where that kind of perf matters.

But I do agree that even if you don't have to worry about cache latency for every single thing you write, it is something you should know about.