Memory optimizations to reduce CPU costs | Hacker News Reader

Memory optimizations to reduce CPU costs

ayende.com

56 pointsjbjbjbjb18 comments

The stunning inefficiency of storing the key with every value, even without any GC-specific issues, should give one pause.

Smaller things are faster to copy etc.,. The fun part is that the opposite is true as well, when you have some constant load on a service, if you make the requests faster then you will have less requests in flight at once (Little's law) and the aggregate memory consumed by those requests while they are in flight will hence be less.

That's not even the point they're really making here, IMO.

The significant decrease they talk about is a side effect of their chosen language having a GC. This means the strings take more work to deal with than expected.

This feels more like this speaks to the fact that the often small costs associated with certain operations do eventually add up. it's not entirely clear in the post where and when the cost from the GC is incurred, though; I'd presume on creation and destruction?

Even without a GC actual strings are potentially expensive because each of them is a heap allocation, if you have a small string optimisation you avoid this for small strings (e.g. popular C++ standard library string types can have up to 22 bytes of SSO, the Rust CompactString has 24 bytes) but I wouldn't expect a GC language to have the SSO.

The cost of a string array is paid on every GC phase. That array may/contains references so the gc has to check each element every time to check if anything changed. An int array cannot contain references so it can be skipped.

edit: There are tricks to not traverse a compound object every time, but assume that at least one of the 80M objects in that giant array gets modified in between GC activations.

That seems like a huge burden, surely not? How often would a GC typically check for hanging references?

That's most of the work performed by a marking GC.

How much a GC is of total cpu cost totally depends on the application, the GC implementation and the language. It's famously hard to measure what the memory management overhead is, GC in production is anywhere between 7-82% (Cai ISPASS2022). I measured about 19% geomean overhead in accurate simulation by ignoring instructions involved in GC/MM in python's pyperf benchmarks.

Is this similar to data locality?

https://gameprogrammingpatterns.com/data-locality.html

Couldn’t one just lazy load and parse as needed instead of loading potentially 40 million rows into memory? Or better yet, if you have that many…databases exist

The given task can be accomplished with not more than a few kilobytes of RAM, a constant independent of the input and output sizes, but unfortunately I suspect the vast majority of programmers now have absolutely no idea how to do so.

Only real programmers know how to do that.

Okay Fermat

i can see how it'd be possible to transform from the input tabular format to the json format, streaming record by record, using a small constant amount of memory, provided the size of input records was bounded independent of the record count. need to maintain position offset into the input across records, but that's about it

but, maybe we'd need to know more about how the output data is consumed to know if this would actually help much in the real application. if the next stage of processing wants to randomly access records using Get(int i), where i is the index of the item, then even if we transform the input to JSON with a constant amount of RAM, we still have to store this output JSON somewhere so we can Get those items.

the blog post mentioned "padding", i didn't immediately understand what that was referring to (padding in the output format?) but i guess it must be talking about struct padding, where the items were previously stored as an array of structs, while the code in the article transposed everything into homogeneous arrays, eliminating the overhead of padding

Padding in the post refers to memory alignment.

If we had an "array of structs" instead of "struct of arrays" it would be: string(8) + long(8) + int(4) + padding(4) = 24 bytes

How about you enlighten us rather than just taunt us with your superior knowledge?

If the “Task” is outputting the JSON for terms to a file, it can be streamed one row at a time - with memory reused after each row is read and the output written. That could be done with a few KB of program space assuming you’re parsing the CSV and outputting the JSON manually instead of using a larger library.

The problem isn’t well constrained because it seems to imply that for some reason it needs to be all accessible in memory, doesn’t specify the cardinality of terms, doesn’t specify whether Get(i) is used in a way that requires that particular interface for accessing a row by number.

If I were to do it, I’d just parse a Page at a time and update a metadata index saying Page P contains entries starting at N. The output file could be memmapped and only the metadata loaded, allowing directly index into the correct Page which could be quickly scanned for a record, and would maybe use 1-2MB of RAM for metadata and whatever Pages are actually being touched.

But like I said the problem is not well constrained enough for even a solution like that to be optimal, since it would suffer from full dataset sequential or random access, as opposed to hot Pages and a long tail.

/shrug specs matter if you’re in the optimization phase

Apparently you're not interested in thinking either, which is another thing I've noticed with many developers these days...

The sibling comment provided a good hint already. All you need to store are some file offsets, amounting to a few dozen bytes.

Thank you for demonstrating your ignorance.

Reply on news.ycombinator.com