Saving 100 terabytes of memory by optimizing 1.1.1.1's DNS cache

There are various ways of implementing this, someone from a C programming background mentioned on option where the heap-allocated record objects aren't fixed size structs, but instead the allocated space is dynamically sized and the struct is just a prefix.

So logically you'd have the equivalent of:

    struct FooRecord {
        int fixed_sized_field;
        char some_other_field;
        string first;
        string last;
        string title;
    }

Physically the compiler would generate something like:

    struct FooRecord {
        long __length__;
        int fixed_sized_field;
        char some_other_field;
        char* first;
        char* last;
        char* title;
    }

Where 'first', 'last', and 'title' are sequentially stored after the struct in the heap memory.

There are variants of the above, of course. Instead of pointers the compiler could use lengths, offsets, or a pointer to the end of the variable length field -- this works because the beginning of the first field is at a fixed offset, and then pairs of pointers delimit the rest.

You can rely on the heap allocator to track the "__length__" instead, or you can encode it into the record explicitly to make "dynamic sized copies" simple.

Windows APIs generally work this way! You create a buffer, put a length in the first field, and then the API call writes a fixed-sized prefix followed by the dynamic-sized fields into the buffer. The 'length' is replaced too, so you know how many bytes to copy out without having to understand the structure.

Database engines go one step further and pack multiple "records" into a single "row". They typically store the fields "packed" at the start of the row with 16-bit length or offset markers at the end for the various dynamic sizes.

Something like:

    fixed_sized_field // Row #0
    some_other_field
    first
    last
    title
    fixed_sized_field // Row #1
    some_other_field
    first
    last
    title
    ... empty space ...
    next_offset      // always populated
    row#1_title_offset
    row#1_last_offset
    row#1_first_offset
    row#1_offset
    row#0_title_offset
    row#0_last_offset
    row#0_first_offset
    row#0_offset  // typically the constant zero

The idea here is that every length is the difference between pairs of sequential offsets. I.e. row#1_title has length (next_offset-row#1_title_offset).

And yet when Prof. Donald Knuth wrote that in 1974 paper[1] it was in this context:

> "The improvement in speed from Example 2 to Example 2a is only about 12%, and many people would pronounce that insignificant. The conventional wisdom shared by many of today's software engineers calls for ignoring efficiency in the small; but I believe this is simply an overreaction to the abuses they see being practiced by pennywise-and-pound-foolish programmers, who can't debug or maintain their "optimized" programs. In established engineering disciplines a 12% improvement, easily obtained, is never considered marginal"

also:

> "In the late 1960's we witnessed a "software crisis", which many people thought was paradoxical because programming was supposed to be so easy. As a result of the crisis, people are now beginning to renounce every feature of programming that can be considered guilty by virtue of its association with difficulties. Not only go to statements are being questioned; we also hear complaints about floating-point calculations, global variables, semaphores, pointer variables, and even assignment statements. Soon we might be restricted to only a dozen or so programs that are sufficiently simple to be allowable"

In a recent comment I mentioned a youtube interview with Rico Mariani, a performance engineer from Microsoft, and he said that he often got called into projects approaching their deadlines and not meeting their performance goals.

In one anecdote he spent a couple of hours with a team and showed how their design could never meat the goal even with the fastest disks, CPUs, memory, and network. And commented how strange it is if they had spent a day at the start of the project whiteboarding out the design against hardware specs at the start of the project - and avoided months of wasted effort - that would be called "premature optimization".

[1] https://dl.acm.org/doi/pdf/10.1145/356635.356640

Only seasoned engineers will understand you are not joking.

Rules 1&2 are about speed, not memory. But also, what do you think the issue with measurement is in this case??

[dead]