10 ms·
If you make something that is performance critical, and in particular if it's concurrent, the normal rule is you avoid allocating on the heap at all. Use object
by alkonaut 9y ago
If you make something that is performance critical, and in particular if it's concurrent, the normal rule is you avoid allocating on the heap at all. Use object preallocated data (just operate on massive lists), or use pools of data etc.
Any language/runtime will support just allocating a large blob of data and then playing with it with code that looks like C.
Effectively once you want to write perf sensitive code in a garbage collectied language you have to stop writing idiomatic code for that language.
That can mean using data orientation (SoA for example is a very non-idiomatic thing to do in most C-like languages and especially OO ones). Not using heap allocation at all for any length of time is definitely non-idiomatic in Java/C#/Python/js etc., but that's what you need to do if you want any kind of performance.
There are two truths here: 1) Any language can be as fast as C and 2) When they are as fast as C, they also look like C regardless what it was to begin with.
- pjmlp 9y ago> Effectively once you want to write perf sensitive code in a garbage collectied language you have to stop writing idiomatic code for that language. Only on GC languages that don't offer proper language features for value types. Sadly most of them failed to gain market share, like Modula-3. Eiffel and D are some of few around that offer such capabilities, and C# has been getting some love from System C# features, with spans, new ref types, and GC regions.
- alkonaut 9y agoYes, C# is slowly getting there (I'm a desktop C# dev since 14 years so I have waited for these features to creep in). Value types certainly help, but in idiomatic C# if you foreach over something you (sometimes) allocate an iterator on the heap. And it's not clear from the syntax when you do. You just have to know that a List<T> doesn't heap allocate its enumerator but most other types do, for example. These details are mostly hidden from you. Using the low level features in C# (in the past structs, preferably in an AoS layout, then Span<T> etc tomorrow) will effectively make it a "Safe C". When you use those, you can't use idiomatic C (linq, heap allocs etc). You effectively agree to use a completely different subset of the language for your high perf tasks, and when you do, it doesn't look like the C# you have in the rest of your app.
- pjmlp 9y agoThen I guess you share my sadness when many Delphi features did not land on C# 1.0, specially in what concerns this kind of programming patterns.
- erik_seaberg 9y agoWe don't need types that mandate the same policy for every value, we need "this value is immutable" and then maybe hints about whether copying or aliasing is likely to perform better at each call site.
- weberc2 9y agoI would be surprised if even non-idiomatic CPython could be as fast as C. Even apart from GC, every function call and property access is many C function calls under the hood. I imagine the other languages listed share similar (though less dramatic) issues (Go has bounds checking while C does not, for example).
- alkonaut 9y agoYes, obviously all the "can be as fast as C" is modulo safety switched off, and using static calls. If bounds checks aren't elided and dynamic calls aren't JIT'ed into single jumps just like a C function - then you can't match C. Which is why in most languages, you have to effectively write C (in that language). Not even sure if it's possible in (C)Python, but in C# it effectively means using a lot of "unchecked" blocks, pointers, etc, obviously skipping any interfaces or other vtable lookups etc. The C# you end up with (only structs and no classes, no heap allocation, lots of raw pointers, lots of unchecked and unsafe etc ) will resemble C a lot
- pjmlp 9y agoQuite true, but the big difference is that you just have to write "C like" code in a specific code path, ideally after validating it with a profiler. In a language like C that isn't an option, and 100% of the code might be unsafe thanks to UB.
- alkonaut 9y agoRight. I'm very happy to see these low level Span<T> things enter C# so it's a much nicer integration than it was in the past when the only option was to just offload the inner loop to a C library. But even that (Writing 10% of your app in C) is a much better proposition than writing all of it in C.
- tankenmate 9y agoLanguages that only support immutable data types, like some functional languages, typically can't use object pools, or if you can underneath the hood there's lots of copying going on that simulates object pools. Having said that good lockless implementations along with good use of the right data structures can eliminate some or all of the data bus overhead (depending on the data types and uses). RCU[0] is one such example of single object immutability that in effect allows for mutable data structures that can handle multi-threaded environments at scale. [0] https://en.wikipedia.org/wiki/Read-copy-update https://en.wikipedia.org/wiki/Read-copy-update
- couchand 9y agoOTOH, immutability affords many more opportunities for safe, precise liveness analysis, and the optimizations that can be performed based on this. Frequently functional compilers produce highly mutative output from immutable inputs. After all, isn't the purpose of a compiler to strip away a level of abstraction? Sure, you can't explicitly use an object pool, but a Sufficiently Advanced Compiler could do a better job anyway.
- zaarn 9y agoA "Sufficiently Advanced Compiler" is probably a magical pipedream though. No compiler has precognition or is directly cabled into the developers brain (Though I wish it was) to tell what they want to express. The compiler might not be able to tell a preallocation is worth the effort if it cannot determine how often a function is called. Preallocs waste some startup time on the first time compared to dynamically allocating on the stack or heap and throwing away afterwards and also leaks memory. The compiler would have to be able to tell wether or not a function will be called often and is timing sensitive or whether it is called rarely and latency doesn't matter or any of the millions of variation in the spectrum between those two extremes. A perfect compiler would have to (essentially) solve the halting problem by being able to tell how programs will behave all the time.
- monsieurbanana 9y ago
- klmr 9y ago> When they are as fast as C, they also look like C regardless what it was to begin with. … Unless your language offers appropriate zero-overhead abstractions. C++, for all its flaws, does this extremely well. Then again, C++ is of course (usually) not garbage collected. The problem with the “write like C” approach is that it forces you to write low-level code, and that is usually messy, not self-documenting, and doesn’t take advantage of advanced type system features (which affects correctness).
- jstimpfle 9y agoProvided that by "extremely well" you mean being able to give up control over allocations, making it easier to spew vectors, and worse, maps, all around the place. I think it was ryg who said on twitter that these abstractions are not really "zero cost". C++ abstractions get you in a mindset that might be detrimental to performance. > The problem with the “write like C” approach is that it forces you to write low-level code No, you have to think in what order to do things. Yes, you have to write low-level code, but not all the time. Ideally you write the low-level code in one place and the high-level code in another place. If you do allocations in your high-level code (which is admittedly what you see in many code bases), you are doing it wrong. (speaking of separation of concerns, for example). This has ramifications on maintainability as well as performance. I'm currently writing a little game engine, where I explore an architecture where these things are neatly separated out. (coincidentally, most allocation is done at compilation time, and much "code" is done by the linker). There is of course still a place for script-style code that lacks an elaborate architecture. And I guess C++ is the right choice to do that if you need "tight loop performance" or need to interface with C code.
- klmr 9y ago> C++ abstractions get you in a mindset that might be detrimental to performance. That certainly depends on the application but having been involved with several high-performance libraries written in C++, I can say confidently that C++ abstractions are largely beneficial. For instance, you can often control and avoid memory allocations (but see below): in particular, if you write algorithms interfaces in the style of the standard library, your code will perform very few, if any, unnecessary allocations, and yet be fairly high-level. > Yes, you have to write low-level code, but not all the time. I was talking specifically in the context of writing low-level C-like code, as discussed by my parent comment. You wouldn’t write “high-level C code” outside of C, there’s no need. > If you do allocations in your high-level code you are doing it wrong. As a blanket statement, I don’t agree with this in C++. If you’re careful you can perform (even dynamic!) allocations in C++. Just make sure that you dispatch to a pool allocator. But of course I agree that this requires care, and lots of code should avoid them.
- jstimpfle 9y ago> SoA for example is a very non-idiomatic thing to do in most C-like languages and especially OO ones Isn't it rather that switching between SoA and AoS is tedious? SOA style itself (using common indices into multiple tables) works ok in C, IMO.
- alkonaut 9y agoYes, SoA is just slightly odd (Doesn't look idiomatic with points[i].X instead of points.X[i]), and the switching is so cumbersome that you have to settle for one way or the other.
- gwbas1c 9y ago> If you make something that is performance critical, and in particular if it's concurrent, the normal rule is you avoid allocating on the heap at all. Use object preallocated data (just operate on massive lists), or use pools of data etc. Which really defeats the point of the garbage collector, because the good ones do that kind of work for you! The good garbage collectors re-use pre-allocated ranges and pools of data. Garbage collection usually works out to a performance / latency tradeoff. (A GC app runs faster than a non-GC app, but has latency.) If I get to the point where latency, even with a pause-free of concurrent GC is a problem, then I know I chose the wrong language.
- alkonaut 9y ago> Garbage collection usually works out to a performance / latency tradeoff. (A GC app runs faster than a non-GC app, but has latency.) I think there are several layers to this. First of all, GC'd data is on the heap, and often you are already doomed if you do stuff (in spread out places) on the heap at all because of cache issues. Secondly, if we consider "normal" applications that have small parts of perf sensitive code, while a majority of the codebase is not (such as e.g. a 3D rendering application where you hit a button and it goes of and renders an image for 1 minute), then you'd have plenty of time to set up your data, and then you just "operate" on it for the critical part of time. The same isn't true in all scenarios. Same thing with e.g. a game engine. It's fine to allocate massive amounts of memory, but then in each frame when you have a 16ms budget you allocate nothing. Because the delay loading a level doesn't matter whether it's 5 sec or 10, but you can't spend 17ms in a frame instead of 16ms. Another problem (and benefit) in most GC'd languages is that the GC is there for developer convenience, and the class libraries know its there so all standard library features (such as just iterating over a collection of items) risks creating new heap allocated objects, which might trigger new garbage collections. In e.g. C# I can't make a standard list with a custom allocator. And I can't "foreach" over something and be sure I didnt' allocate etc. > A GC app runs faster than a non-GC app, but has latency I didn't mean to compare an app that does "new Foo()" in the inner loop with one that does "malloc(...)" in the inner loop, I was trying to make the point that you can't do either in the critical part. > then I know I chose the wrong language. Right, but the thing is you might have chosen the perfect language for 90% of your code. The language choice might be too late to change and you just need that concurrent inner loop (rendering loop, encryption pass, whatever) to be quick, and the solution is a lot of time to just allocate nothing.
- Kapura 9y agoI came into the comments to say basically what you said here. Trying to avoid GC? Preallocate! For context, I'm a game developer working in Unity. We do basically all of our dev in C#, which is a language I love. But because it's garbage collected, and you can see performance hits when the GC runs. In VR dev especially (targeting 90 FPS) this is unacceptable. So we profile, look to see where we're allocating anything onto the heap and figure out a way to cache it or re-implement it in a way that makes no garbage. We recently shipped a mobile VR experience and one of the best parts was being able to profile my gameplay code and seeing the '0B's next to its allocations every frame. I understand that this may not work for everyone, and I fully believe that CloudFlare's got some talented engineers on the team, but there are ways to think about and structure programs in a C-like fashion so that you're more cognizant of the memory you are allocating and using from the heap.
- corndoge 9y agoPlease stop prefacing comments with phrases to the effect of "I came here to say this", it is already obnoxious on Reddit and is getting annoyingly frequent on HN as well. No added meaning. I care what you have to say; that you came here to say it is irrelevant. https://news.ycombinator.com/item?id=15683745 https://news.ycombinator.com/item?id=15683745 https://news.ycombinator.com/item?id=15590466 https://news.ycombinator.com/item?id=15590466 https://news.ycombinator.com/item?id=13614442 https://news.ycombinator.com/item?id=13614442 https://news.ycombinator.com/item?id=14306868 https://news.ycombinator.com/item?id=14306868 https://news.ycombinator.com/item?id=14327156 https://news.ycombinator.com/item?id=14327156 https://news.ycombinator.com/item?id=14532140 https://news.ycombinator.com/item?id=14532140 https://news.ycombinator.com/item?id=14531421 https://news.ycombinator.com/item?id=14531421
- always_good 9y agoYour criticism only applies if they had said nothing beyond their first sentence. Sure, their first sentence is irrelevant, but it's forgivable since they elaborate beyond it.
- 9y ago
- rbehrends 9y agoCareful here. Let's take a simple example of allocation-heavy vs. allocation-light code in OCaml: open Batteries let bench name fn = let tstart = Unix.gettimeofday () in let result = fn () in let tend = Unix.gettimeofday () in Printf.printf "%-20s %.3f seconds\n" name (tend -. tstart); result let iterations = 100000 let count = 1000 let insert_list_test () = let result = ref 0 in for i = 1 to iterations do let work = ref [] in for j = 1 to count do work := j :: !work done; work := List.rev !work; result := !result + List.length !work done; !result let insert_list_test_rec () = let rec build_list i n acc = if i > n then acc else build_list (i+1) n (i :: acc) in Enum.map (fun _ -> build_list 1 count [] |> List.rev |> List.length) (1--iterations) |> Enum.fold (+) 0 let insert_dynarray_test () = let result = ref 0 in for i = 1 to iterations do let work = DynArray.create () in for j = 1 to count do DynArray.add work j done; result := !result + DynArray.length work done; !result let main () = let x1 = bench "linked lists" insert_list_test in let x2 = bench "linked lists (rec)" insert_list_test_rec in let x3 = bench "dynamic arrays" insert_dynarray_test in assert (x1 = x2 && x2 = x3) let () = main () As it turns out, this gives us the following results on my laptop, give or take a few hundreds of seconds: linked lists 0.648 seconds linked lists (rec) 0.657 seconds dynamic arrays 1.295 seconds The reason that the linked list implementation (functional or imperative) is faster is that OCaml's GC uses a bump allocator for young objects, with allocations being inlined by the compiler; this essentially makes the linked list implementation behave like an arena allocator and is faster than the dynamic array version (which has to resize and copy the underlying array several times), despite having to do a gratuitous list reversal and doing an O(n) length calculation. (Note that this is not specific to OCaml: Most JVM GCs do the same thing.) The problem that Go has here that it's GC is neither generational nor compacting, so it can't do that, so there's a fairly high constant overhead per allocation, whereas OCaml's or the JVM's temporary allocations are only marginally more expensive than alloca(). Note that there can be good engineering reasons to have a non-generational, non-compacting GC (for starters, compacting GCs make C interoperability more difficult). So, yes, if you have such a GC, you do have to watch out for avoiding extraneous allocations.
- panic 9y ago
- davemp 9y agoI think there’s a caveat that the language needs to support inline assembly.
- Touche 9y agoIt doesn't. Even JavaScript supports preallocating.
- masklinn 9y agoNot really. You can preallocate a bunch of objects in a big freelist (or multiple freelists) and manipulate that.
- davemp 9y agoManual memory management is just one aspect of performance. If you want to compete with C you’re gonna have to be able to hand tune some bottlenecks. The compiler isn’t going to produce optimal code.
- gpderetta 9y ago> There are two truths here: 1) Any language can be as fast as C and 2) When they are as fast as C, they also look like C regardless what it was to begin with. Hence the maxim: "The determined Real Programmer can write FORTRAN programs in any language." It applies to C as well.
- vidarh 9y agoDepends how long running the process needs to be, and how allocation heavy it gets. My first large web app was old enough that we did it in C++ as CGI... One of the first performance optimizations we did was accept that most object lifetimes roughly coincided with the end of the request, so we simply didn't deallocate anything and let the OS just free the whole thing at once. You can do the same in most GC'd languages by just tuning GC limits. (the second performance optimization we did was to to statically link everything; loading a static binary that's constantly in the cache is/was very fast; and it was enough to make CGI surprisingly competitive in terms of performance) Preallocation certainly has its place too, but in this case we tried custom allocators and it simply didn't make much difference. So before rewriting your code, see if you can simply turn off deallocations/GC without too much memory pressure.
- CyberDildonics 9y agoIn your case you likely could have made your stack large and used that in some areas while making the data segment of your binary large and using that for other areas. Since the executable is memory mapped anyway the OS would allocate memory in large chunks without the overhead of trying to organize a heap.
- vidarh 9y agoDoing just straight allocations in C++ without de-allocations has pretty much same effect. It'll ask for memory from the OS in large chunks, and without anything ever being de-allocated, unless your allocator is too smart for its own good, allocation can be extremely cheap. I did actually try a custom allocator that'd just hand out sequential pieces of memory from a large buffer without keeping track of it at all, but if it made things any better, the effect was small enough that we couldn't reliably measure it.
- CyberDildonics 9y agoNot exactly. You save on deallocations, but you still have the allocator doing system calls and then fitting the sizes you want into the heap. Granted the heap probably doesn't have to work hard to make them fit, but it still allocates. I don't know if under the hood system calls to mmap or virtual_alloc block other processes calling the same functions.
- tareqak 9y agoIs there a way for the compiler or the runtime to be designed such that it can detect that these heap allocations of the same "shape" and similar size are happening with sufficient frequency/regularity that some optimization is possible?
- cocoa19 9y agoYes, it can be done. I don't know about Go, but this is already done for other languages. In C/C++, you can override the memory allocation functions (malloc, delete, new, free, etc) based on the type of heap objects you are going to handle. Most or all C and C++ standard libraries come with generic allocators that work OK in most scenarios, but not optimally for specific scenarios.
- thecompilr 9y ago> If you make something that is performance critical, and in particular if it's concurrent, the normal rule is you avoid allocating on the heap at all. This is a very synthetic workload, and all allocation were done by the standard library.