The compiler will optimize that away • Hacker News Board

Re: The compiler will optimize that away

#321

Post by jolux » Tue, May 04, 2021, 3:26 PM UTC

blakehaswell wrote: post #311

jolux wrote: post #117

Earlier quoted context omitted.

To me, the goal of language implementations should be to make the most maintainable code also the fastest code. I shouldn't have to worry much about the performance characteristics of my software outside of general concerns about algorithmic complexity.

At the end of the day our software is going to run on real machines, sending data across real networks. I feel like we'll always be leaving performance on the table if we don't understand the characteristics of the hardware we're developing on. I can build a cubby house in the backyard (low performance system) without understanding the the physical characteristics on the materials I'm using, but if I want to build a…

> I feel like we'll always be leaving performance on the table if we don't understand the characteristics of the hardware we're developing on.

Absolutely. Mine is not a suggestion to ignore performance, but to build languages that push programmers towards doing the right thing for performance and maintainability. These do not have to be at odds, except often at the extreme of performance.

Re: The compiler will optimize that away

#322

Post by godshatter » Tue, May 04, 2021, 3:30 PM UTC

kaba0 wrote: post #292

dahart wrote: post #284

Earlier quoted context omitted.

FWIW, I profile intensive applications all the time, it's my job. You're right about the existence of hot spots, but that's not particularly relevant to my point or the author's. Just because one spot is hot doesn't mean you should rationalize using lazy or bad-practices programming on the rest. Just because you don't see a bottleneck somewhere when you profile doesn't mean it'll stay that way when other processes wa…

I apologize for my cocky reply. I just meant to point out that SoA vs AoS or an even slower data structure is not necessarily relevant for all programs. > The main perf problem with using linked lists in high level languages is not the fact that they cause cache-incoherent access, it's worse, it's the fact that they allocate and deallocate memory constantly which is much much slower. This is not true though; at least…

>So the usual linked list gets appended a few times is close to optimal, iteration has the same cost as in lower level languages with pointer chasing (usually a bit more because objects usually have headers that take quite some space, less of them potentially fitting into cache). It even has some advantage in that a modern compacting GC may move the objects close to each other.

I wonder why array-backed linked lists aren't more of a thing. I've used those before in C in hobby projects. You allocate an extendable array of nodes and the nodes next and/or prev pointers become indices in the array (although pointers would still work). Added nodes go on the end, deleted nodes stay where they are and just aren't referenced. If there is high churn, do something to keep track of inactive nodes to fill next. You're still spamming around an area of memory when iterating the list, but it's at least confined to one guaranteed contiguous block and you're only allocating to extend the array and not doing a lot of allocating and freeing of memory. You still have the memory overhead of the next/previous indices, though, so fewer nodes fit in cache than otherwise would.

Re: The compiler will optimize that away

#323

Post by dahart » Tue, May 04, 2021, 6:01 PM UTC

godshatter wrote: post #322

kaba0 wrote: post #292

Earlier quoted context omitted.

I apologize for my cocky reply. I just meant to point out that SoA vs AoS or an even slower data structure is not necessarily relevant for all programs. > The main perf problem with using linked lists in high level languages is not the fact that they cause cache-incoherent access, it's worse, it's the fact that they allocate and deallocate memory constantly which is much much slower. This is not true though; at least…

>So the usual linked list gets appended a few times is close to optimal, iteration has the same cost as in lower level languages with pointer chasing (usually a bit more because objects usually have headers that take quite some space, less of them potentially fitting into cache). It even has some advantage in that a modern compacting GC may move the objects close to each other. I wonder why array-backed linked lists…

Agreed, especially for high level languages and application level linked list usage. Worth mentioning I think the good linked list libs usually do this under the hood, and kernel & allocator level linked lists are always doing this. People implementing simple linked lists themselves, and/or copy-pasting the kind of code you get by searching for simple code examples (like the link in my sibling comment here), that's when they end up with very poor performing linked lists.

A closely related concept to what you're describing is internal storage linked lists [1], meaning the class/node contains the link(s) and is specialized for one particular kind of data, which often makes it more compact, and easier to allocate a block of nodes in a single call.

Anyway, I'd guess a big reason it's harder to find array backed lists when searching for linked list implementations is just because it's more advanced and may introduce memory management topics into articles and blog posts that the author doesn't want to cover. But I agree, once you use array-backed lists, the common examples of linked lists you can find online where new is used twice per node, once for a generic node, and once for the payload, seems ridiculously wasteful. This is the kind of thing I meant earlier - best practice would be to avoid a naive bad linked list even in code that isn't a hot spot. Time doesn't have to be spent optimizing it, and it doesn't need to appear as a hotspot, to know it should be avoided.

[1] https://en.wikipedia.org/wiki/Linked_list#Internal_and_exter...

Re: The compiler will optimize that away

#324

Post by dahart » Tue, May 04, 2021, 6:15 PM UTC

kaba0 wrote: post #313

dahart wrote: post #307

Earlier quoted context omitted.

> at least the JVM most definitely doesn’t do that, and I’m sure other state-of-the-art GCs neither, like V8. Which implementation are we talking about here? Do you mean JVM internal linked lists, or user allocations of linked list nodes? I was talking about implementations such as (first Google result for "Java linked list implementation") https://www.geeksforgeeks.org/implementing-a-linked-list-in-... > First of al…

What are the specific situation that we are talking about? Of course needless creation of non-single-use objects will have a cost, but object reuse via pools may be even worse than creating non-escaping objects in a tight loop. The “problem” with high level languages is the complexity of their runtimes - you can’t easily reason about what and how will get optimized. It can change from version to version so one should…

> The “problem” with high level languages is the complexity of their runtimes - you can’t easily reason about what and how will get optimized.

Yes, agreed. This is the point the author was making, and noting that we have room to actually improve the languages, and make some basic optimizations easier to think about and code explicitly.

> object reuse via pools may be even worse than creating non-escaping objects in a tight loop.

When does this happen in practice, and how likely is it? What does it imply about object lifetime if your objects don't escape, and why wouldn't you be re-using an object on the stack or local scope instead? How often would replacing a non-escaping object creating with a re-use that escapes be a realistic alternative? I'm sure a contrived case can be setup, but this seems like an unlikely explanation to me as general advice. It's bad practice to hope your objects don't escape, and difficult to ensure. In general, if you want higher performance, then avoid using new in hot spots. The difference is often an order of magnitude in an flat O(n) loop.

Re: The compiler will optimize that away

#325

Post by purplerabbit » Tue, May 04, 2021, 6:43 PM UTC

slifin wrote: post #58

beagle3 wrote: post #45

Earlier quoted context omitted.

> Somehow over the years I've found that the animals/cars analogies given in OO tutorials are one of the few places that fit well with the model. Yes, and I've never actually needed to implement a cat or a cow in any project :) The other thing for which OO works much better than plain data is GUIs - and I think it is not a coincidence that OO popularity exploded together with the the coming-of-age of GUIs. The other…

OO is a tree and html (UI) on a page is a tree The problem is when you want to go to page two and want to display the same data as page 1 but in a different configuration OO is suddenly terrible because the data is the wrong shape, you should hold your data as a graph then derive trees out of it to satisfy views OO is not good for UIs unless you have one page and the contents on that page is static and doesn't change…

been thinking about this comment since I read it and really love it (even though OO isn't always a tree). This graph tree relationship seems central to the successes and failures of many implementation approaches I've seen over the years. Thanks for sharing.

Re: The compiler will optimize that away

#326

Post by kaba0 » Tue, May 04, 2021, 8:03 PM UTC

dahart wrote: post #324

kaba0 wrote: post #313

Earlier quoted context omitted.

What are the specific situation that we are talking about? Of course needless creation of non-single-use objects will have a cost, but object reuse via pools may be even worse than creating non-escaping objects in a tight loop. The “problem” with high level languages is the complexity of their runtimes - you can’t easily reason about what and how will get optimized. It can change from version to version so one should…

> The “problem” with high level languages is the complexity of their runtimes - you can’t easily reason about what and how will get optimized. Yes, agreed. This is the point the author was making, and noting that we have room to actually improve the languages, and make some basic optimizations easier to think about and code explicitly. > object reuse via pools may be even worse than creating non-escaping objects in a…

I’m not disagreeing with you, and as a very general advice, less allocation is better of course.

My point was more along the way that sometimes very non-intuitive (from a low-level perspective) solutions may optimize better, because that’s what the compiler writers optimized for.

And object pools at least in Java is not necessarily good. The first go at it should be the plainest implementation one can imagine (on a micro level. Of course architecturally it is important to think about optimization, like whether it will be a class or an array, etc.)

Re: The compiler will optimize that away

#327

Post by Sohcahtoa82 » Wed, May 05, 2021, 10:20 PM UTC

> You may even realize that all of that enterprise cruft is not really necessary

I will never understand why so many Java developers insist that every public value must be implemented as a private value with get/set with no exceptions.

Or that every class needs to extend an abstract class that implements an interface.

Haven't they heard of YAGNI?

Re: The compiler will optimize that away

#328

Post by Sohcahtoa82 » Wed, May 05, 2021, 10:31 PM UTC

astrange wrote: post #153

quadcore wrote: post #141

Earlier quoted context omitted.

I dont know if you've noticed, but most programmers actually do care about performances. They just are bad at it. Software are slow precisely because programmers dont get it: optimising all the code will make slow software. They spend their budget optimising 99% of the code and end up with no more money to make that last 1% fast. For real (game engine programmer speaking). Plus optimising all the code make all the co…

Usually simpler code is better. I used to see a lot of mistaken "high performance" code where someone has unrolled all of the loops because they think unreadable code goes faster, though maybe people have gotten better about this? (OpenSSL is an example here.) Unfortunately not all kinds of slowness only happen in hotspots. This is true for CPU cycles, but if an occasional task uses all memory, it's going to mess up…

I wonder where the trade-off is for loop unrolling.

Like, unrolling a `for` loop that only has 5 iterations makes sense. But if you have 100 iterations, then the larger memory footprint of all the code might actually make it slower than just keeping the `for` loop.

In some cases, you can use Duff's Device. https://en.wikipedia.org/wiki/Duff%27s_device

Re: The compiler will optimize that away

#329

Post by Sohcahtoa82 » Wed, May 05, 2021, 11:07 PM UTC

beagle3 wrote: post #45

lordnacho wrote: post #13

Good article. My own thinking when coding performance is also towards data oriented approaches. For example Bevy in Rust. If stuff needs to be fast, it needs to be in cache. To do that, have everything nicely packed so you only ask for a chunk as often as you need. Then when you need it, it's already there. Thing about old fashioned OO is it's often fine enough for your run-of-the-mill CRUD app. If you look at the la…

> Somehow over the years I've found that the animals/cars analogies given in OO tutorials are one of the few places that fit well with the model. Yes, and I've never actually needed to implement a cat or a cow in any project :) The other thing for which OO works much better than plain data is GUIs - and I think it is not a coincidence that OO popularity exploded together with the the coming-of-age of GUIs. The other…

> The other canonical example of OO - "Shapes" - doesn't actually work well at all; It doesn't work better with "plain data", but it exposes the fallacies of trying to use OO inheritance to model the real world.

Shapes work well, but people do the wrong things with them, as you state...

> Every square is a rectangle, so square should inherit from rectangle ... but, you can't stretch width and height independently in a square, so it's not really a rectangle, etc. etc.

A square is a just a rectangle where the length and width happen to be the same size and shouldn't be its own class. Books and websites teaching inheritance should stop trying to use it as an example.