Nazi Germany produced two wartime diaries of equal literary and historical significance but written from the most different perspectives conceivable. Victor Klemperer wrote furtively, in daily dread of transport to an extermination camp, a fate he was spared by the firebombing of Dresden. Ernst Jünger, by contrast, had what was once called a “good war.” As a bestselling German author, he drew cushy occupation duty in Paris, where he could hobnob with famous artists and writers, prowl antiquarian bookstores, and forage for the rare beetles he collected. Yet Klemperer and Jünger both found themselves anxiously sifting propaganda and hearsay to learn the truth about distant events on which their lives hung.
One might ask why it has taken 70 years for Jünger’s diary to appear in English translation, for there is no more detailed account of the occupation from the German point of view. But Jünger was always controversial, up to his death in 1998 at the age of 102. In Germany, polite opinion has never forgiven him for Storm of Steel, his memoir of World War I that saw in the experience of combat an ultimate test of manhood. “The finest, most visceral account of battle since the Iliad,” according to the New Statesman, his book made him a hero among German nationalists and ensured his privileged status in Nazi Germany. As it happens, Jünger was anything but a Nazi.
Born in 1895, the son of a chemist, Jünger got off to an unpromising start. A chronic discipline problem, he was repeatedly forced to change schools until at last in 1913 he lied about his age, joined the French Foreign Legion, and found himself in the Algerian desert. By the time that the German foreign office could extricate him, World War I was looming. He enlisted immediately, and, for the first time in his life, he flourished.
World War I, for Jünger, was not the grinding mechanized mass-slaughter we know from the war poets. Serving for the duration, he watched the replacement of sanguinary frontal assaults by storm-troop tactics, where small detachments of well-armed soldiers trained in hand-to-hand combat would overrun selected points and break through the enemy’s rear. Such a form of warfare rewarded personal initiative and bold leadership, which Jünger took as the principal lesson of the war. By the time he won the Pour le Mérite, Germany’s highest military honor, he had already been wounded 14 times in combat.
After the war, Jünger studied zoology, where he cultivated the acute observational skills that distinguish his writing. He came to despise the Weimar Republic and flirted with nationalist groups, including—briefly—the Nazi Party. In 1926, he sent one of his books to Hitler, who proposed a meeting. By the time it fell through, Jünger was already having misgivings. He decided that Nazi racial ideology was embarrassing (“peinlich”), and he thereafter held aloof, making certain that he and Hitler never met personally.
Jünger was far too capricious and eclectic a thinker to fit into any straitjacket. Had the Nazis read Storm of Steel carefully, they would have noticed that it was strikingly free of nationalist or political content. Jünger’s belief system was an idiosyncratic mysticism that drew equally from science and religion; by temperament he was essentially a German romantic, for whom intense personal experience led to an understanding of the fundamental unity of nature. As a result, his circle of friends was as wide as could be, including the dadaist artist Kurt Schwitters and even Communists or Communist sympathizers such as Ernst Niekisch.
All this brought him into open conflict with Joseph Goebbels, who recognized an enemy in Jünger and attacked him in print. For his part, Jünger never joined the Nazi Party, and he refused to let his writings appear in Nazi publications. Twice his rooms were searched by the Gestapo, looking for incriminating documents about his Communist acquaintances. Under the circumstances, it defies belief that Jünger ever dared keep a diary, let alone one of such uninhibited candor as the one he kept from April 1941 to August 1944 during his tour of duty in occupied Paris.
Shortly after his arrival, a German officer was assassinated in Nantes and Hitler decreed that a hundred randomly selected hostages be shot in reprisal. Before their execution, they wrote final letters, which Jünger was given to translate. Affected by their dignity and composure, he was struck by how often the same words recurred, particularly courage and love. The conduct of those facing death always interested him, and as the war progressed, he began collecting accounts of shipwreck and starvation.
The most disagreeable act Jünger was called upon to perform was supervising the execution of a recaptured deserter. Jünger pitied him (he had been denounced by the French girlfriend who had been concealing him) and even considered backing out of the ordeal by feigning illness. But he decided it would be “shabby” to foist the duty on someone else and that he could see it through with less brutality than anyone else. The account of that execution, carried out in the pleasant Bois de Boulogne, has drawn more criticism in Germany than any other incident in the diary. Jünger was condemned for reshaping his published account from the version in the original manuscript, which he indeed did, although not to minimize his culpability but to sharpen its literary quality.
But this was the point of the criticism, that by taking refuge in a self-indulgent aestheticism, Jünger fled the moral choices imposed by the war. To be sure, to dip into the diary at random is to get the impression of a dandy and flâneur. A literary celebrity, Jünger enjoyed entrée to the highest circles. He could visit Picasso and Braque in their studios and debate their art in fluent French, or ponder the meaning of dreams with Jean Cocteau (“someone who dwells in a special, but comfortable, hell”), who sent him passes to screenings of surrealist films. With seemingly endless leisure time, he took long walks and indulged his habit of exploring cemeteries, writing lyrical but precise accounts of the tombstones, their inscriptions, and the plant and insect life teeming around them. He even found time to contemplate the city’s curious dog cemetery.
At times Jünger does not even seem to know he was fighting a war. After the D-Day landings, he went to bed reading a 14th-century chronicle of the life of Saint Louis. Not even an air raid could ruffle his coolness; his entry of September 15, 1943, is typical. He began the day interpreting one of his tormented zoological dreams, later inspecting the Gothic church of Saint-Séverin with his Parisian mistress, and then later, at the sound of the air sirens, went to his hotel rooftop to observe the bombardment and see planes torn apart by flak and watch as “something of considerable size, sepia-brown, gathered speed as it fell—most likely a man attached to a smoldering parachute.” Yet after all that, as he did every night, he could still take a book to bed:
Read further in Huxley, whose lack of structure is tiresome. His is a case of an anarchist with conservative memories who opposes nihilism. In this situation, he ought to employ more imagery and fewer concepts. As it is, he seldom exploits the real strength of his talent.
Jünger could have been writing about himself here. It is this ice-cold detachment—the plummeting pilot and then the literary criticism—that makes him repellent to the casual reader.
But to read the diary in chronological order is to realize that Jünger’s submersion in art and literature was his way of preserving his humanity while serving the machinery of a lethally violent state. One way of doing this was through a voracious program of reading, chiefly literature and history, often reading two or three books at once. One is not surprised at the German and French reading but at the abundance of English writers, whom he read in the original—Melville, Joyce, Poe, Conrad, Kipling, Thomas Wolfe, Thornton Wilder, the Brontës, ad infinitum. The range is also remarkable. Jünger pivots from the 1772 fantasy Diable amoureux to a biography of the painter Turner to Crime and Punishment. And throughout the entire diary, one finds him reading the Bible, cover to cover, which he began shortly after his posting to Paris.
One is surprised to see how little Jünger has to say about the actual course of the war. Major events, such as the attack on Pearl Harbor or Hitler’s declaration of war on America, pass by unmentioned or with a stray comment. Here we see the fatalism of the jaded World War I veteran, who has long stopped believing that “decisive” battles decide anything. But Jünger’s real interest, to which he pays acute attention, is the process of moral corruption that he sees as the inescapable legacy of the lemurs, his code word for the Gestapo and other servants of Nazi tyranny. Nowhere is this seen more clearly than in his obsessive recording of all that he can learn about German war crimes.
For American readers curious about the extent of German knowledge and complicity in genocide, this is the central question. Even as well-connected a celebrity as Jünger had to rely on the occasional visitor from the Russian front to learn firsthand of Nazi atrocities. It is not until November 4, 1941, five months after the invasion of Russia, that he first records a “hideous mechanism for executing prisoners,” which required them to strip and be measured by a weighing machine that was actually a lethal air gun. By March 1942, he was fully informed about the activities of the Einsatzgruppen, the units charged with the organized killing of political enemies, primarily Jews, behind the front lines: “certain butchers…who have singlehandedly slain enough people to populate a midsize city.”
If I correctly understand his cryptic entry, Jünger learned of the results of the Wannsee Conference from General Jodl, chief of the operations staff, on February 8, 1942, just 19 days later. And so when Jünger described his first sight of yellow stars in Paris on June 7, 1942, he knew full what it portended.
On Rue Royale, I encountered the yellow star for the first time in my life. Three young girls who were walking past arm in arm were wearing it. This badge was distributed yesterday, and those who received it had to part with a point from their clothing ration in return. I then saw the star more frequently that afternoon. I consider things like this, even in my own personal history, a significant date—I was immediately embarrassed to be in uniform.
For all the criticism that Jünger has served up a self-serving exculpatory diary, the truth is that he leaves his most selfless acts unmentioned. It is known that he gave advance warning to Jews facing deportation: The writer Joseph Breitbach was one, as he subsequently confirmed, and Walter Benjamin was possibly another.
None of this, for obvious reason, could be committed to paper, nor could the names of Adolf Hitler or any of his henchmen. Instead, their appearances are marked by Jünger’s felicitous code names. Joseph Goebbels, the Nazi chief propagandist, is “Grandgoschier,” a character from Rabelais’s Gargantua and Pantagruel meaning “Big Throat.” SS Chief Heinrich Himmler is “Schinderhannes,” the name of a notorious German highwayman but also a pun on horse knacker. And Hermann Goering is simply “Head Forester,” citing the most fatuous of his many official titles.
Jünger thought a great deal about the mystic and symbolic power of sounds, and he reserved his most apposite pseudonym for Hitler, “Kniébolo,” a name that is at once menacing and absurd. It suggests a kneeling demon (Diabolos), a leitmotif of the diary as Jünger became ever more convinced of Hitler’s essentially Satanic character—in the literal biblical sense. Reducing Hitler the man to Kniébolo was congenial to Jünger’s way of dealing with the world, which was through metaphysical symbols and archetypes. One begins reading the diary with mild annoyance at Jünger’s fastidious recording of his dreams but soon realizes that they are part and parcel of the same actively questing mind, in which conversation and reading, art and dreams, all strain to make sense of the senseless. The result is a miracle of the diarist’s art, a diary as eventful and consequential as those of Samuel Pepys or James Boswell, but with an inner life.
Given the exceptional importance of Jünger’s diary, it deserved an impeccable translation and editorial notes. Distressingly, it has not received them. While the foreword delivers an excellent account of Jünger’s life and the importance of the diary, it does not say nearly enough about its publication history and revisions over the years. Unaccountably, and senselessly, it omits his preface to the original publication, Strahlungen (Rays or Emanations). There he gives his fullest account of how he edited the diaries for publication, refusing to censor or retouch, even for purposes of clarity, while skipping some personal details for reasons of taste (unlike James Joyce, whose Ulysses “registered every possible circumstance for using the toilet”).
The missing foreword also sheds light on the great question hanging over the diary, which is why Jünger, who was intimately associated with many of the July 20 conspirators against Hitler, did not join the coup. Above all, it would have been valuable to hear Jünger’s justification of keeping a wartime diary in the first place: “In a totalitarian state it remains the last possible conversation.”
A German Officer in Occupied Paris has won universal praise, but no reviewer has called attention to its errors of translation. For example, Hitler is described as insisting on taking personal command of “two tank battalions” after the D-Day landings, when the German text reads “two panzer corps,” the difference between 2,000 men and 100,000. Literary translators are not expected to be military historians, but, given the topic, they might have consulted one.
Other errors show embarrassing carelessness. For example, the final entry of the book describes the dramatic entry of American troops in Jünger’s town on April 11, 1945. Just before their arrival, the soldiers commanding the local artillery unit destroyed their guns and dispersed, while their commander, “who wanted to escape in civilian clothes, committed suicide”; in fact, according to the original German text, he was killed by his own men.
Even worse is the rendering of the entry for August 10, 1944, when Jünger was preparing to abandon Paris on the eve of its recapture by the Allies. On that day, we are told, he bought a small notebook like those he used “when I was a journalist in more stirring times.” The reader will wonder what times were more stirring than the summer of 1944. In fact, the German text explains quite clearly that he bought a notebook “of the sort which in more dangerous situations I substitute for the big diary.”
We naturally assume that a translation published by a university press will achieve a minimal accuracy in translation, and we do not expect our reviewers to search for errors. I would not have spotted these errors (and others) had I not by chance read the German original shortly before the translation appeared.
For the moment, though, it is all we have in English. Even in its imperfect and incomplete form, it should be read by anyone with a serious interest in the horrific events of the past century. There is still ample material here to debate the moral choices made—and evaded—by Jünger, and to ponder Cocteau’s final verdict, who liked Jünger but whose aloofness troubled him: “Some people had dirty hands, some had clean hands, but Jünger had no hands.”
Household appliances will become easier to repair thanks to new standards being adopted across the European Union.
From 2021, firms will have to make appliances longer-lasting, and they will have to supply spare parts for machines for up to 10 years.
The rules apply to lighting, washing machines, dishwashers and fridges.
But campaigners for the "right to repair" say they do not go far enough as only professionals - not consumers - will be able carry out the repairs.
The legislation has been prompted by complaints from consumers across Europe and North America infuriated by machines that break down when they are just out of warranty.
Owners are usually unable to repair the machines themselves - or find anyone else to do it at a decent price - so are forced to buy a replacement.
This creates waste and fuels global warming through the greenhouse gases created in the manufacturing process for new machines.
In the US, around 20 states are said to have right to repair legislation in progress.
Under the European Commission's new standards, manufacturers will have to make spares, such as door gaskets and thermostats, available to professional repairers.
These parts will have to be accessible with commonly-available tools and without damaging the product.
Campaigners say individual consumers should also be allowed to buy spares and mend their own machines. But manufacturers said this would raise questions about risk and liability.
Image copyrightGetty Images
Instead, manufacturers will have to ensure that key parts of the product can be replaced by independent professionals.
If British firms want to sell into Europe after Brexit they will have to follow the new rules, which apply from April 2021.
'Massive step'
It is estimated that the new standards will ensure that appliances have a longer life. The rules also include provisions to make appliances more energy efficient.
For example, star ratings for the energy efficiency of appliances will be ratcheted up. Current regulations are seen to be outdated, with more than 55% of washing machines sold in the EU ranked A+++ on the label.
The move could directly save €20bn on energy bills per year in Europe from 2030 onwards - equivalent to 5% of EU electricity consumption.
Chloe Fayole of environmental group Ecos said: “From the US to Europe, people are demanding their right to repair things they own because they’re tired of products that are designed to break prematurely.”
Libby Peake from the UK Green alliance told BBC News: “These new standards are a massive step in the right direction and could result in nearly 50 million tonnes of CO2 emissions savings.”
But Stephane Arditi of the European Environment Bureau said: “When repair activities stay in the hands of a few firms, we’re missing an opportunity to make it more affordable and readily available.
“Small independent repairers can make a great contribution to the economy and our society. We need to help them do their job.”
Welcome to part 3 in this series covering all the data structures you really need (kind of).
In part 1, we saw that the best way to store most data is just to use a big old array and that with some tricks we can allocate this array so that the objects in it have fixed indices and permanent pointers.
In part 2, we saw how to fix the most glaring problem with these arrays — that it is kind of expensive to find things in them — by adding search indices that let us quickly find any subset of objects that we are interested in.
In this part, we will tackle a final problem. When we created our bulk data arrays, we assumed that all objects were fixed size so that we could fit their data into a single struct and store the bulk data as just an array of such structs:
How can we store the object names and children in a good way?
Capped Size
The simplest way of handling dynamically sized objects is to just get rid of the problem. If we set a maximum size for our strings and arrays, we’re back to having a fixed size struct, with the string and array data stored in the struct itself:
Now we can just make an object_t[] as before and have all the data in there.
Capping sizes is always a bit scary, because what if we set the cap too low and hit the limit? Personally, I feel a little bit dirty every time I do this. I think it’s PTSD from run-ins with some really ridiculous size limits, such as MAX_PATH = 260 in Windows.
But there are a lot of situations where having a maximum size is fine. There is a big difference between locking a maximum size down in a file format or an OS API, where it might live for 50 years, causing headaches to generations of programmers, versus just having it in your runtime, where you can change it whenever you want without worrying about compatibility with old software. You can start with a fixed size and change to something more advanced when you need to. Code doesn’t have to be “future-proof” if it is easy for future you to change it.
Also, if you are writing code for just one particular game and not a generic engine, you don’t need to support anything beyond what your game needs. If you only support four players, your player arrays can all be players[4]. And anything that’s just for internal use, you can limit to whatever you find reasonable. For example, object debug names can probably be s[64] without any problems. Longer names are too hard to read anyway.
Also, keep in mind, that even if you don’t specify an explicit maximum size, there is probably a practical limit anyway. If you have too many things you will eventually overflow an uint32_t, run out of memory or drive the FPS down to the point where your app is unusable.
Judicious use of maximum sizes can simplify the code a lot. Of course, it doesn’t always work:
Some things can get arbitrarily large.
Some things have a limit, but the limit is so high that you will waste a lot of memory by using a fixed-size array.
Some things have a small limit, but enforcing the limit is more trouble than its worth.
As an example of the last case, consider your application’s window system. You could probably limit the number of windows to 128 because no sane user will want to deal with more than 128 open windows. (Note that this does not apply to tabs — many users are perfectly happy having a couple of thousand Chrome tabs open.) Using a fixed size of 128 won’t waste much memory either since you only need one global window array.
But… if you decide to set a limit of 128 windows, you have to decide what to do if the user tries to open more than that. You probably don’t want to crash. Do you beep? Show an error message? What if the window you can’t open is the window that was supposed to show the error message? Now you have this extra code path in your code, that you have to write, maintain and test. An extra place where things can go wrong. It might be easier to just support an “unlimited” number of windows and let the users dig their own graves.
Heap allocation
If we can’t use a fixed-size array, the next simplest thing is to just use an off-the-shelf STL object, such as std::string or std::vector.
What happens when we use one of these types? STL will allocate data for the string and the vector on the system heap. Each string and vector gets its own individual little memory allocation, so we have a situation that looks something like this:
STL memory layout.
If we have an std::vector<object_t> with 10 000 items in it, we will use one memory allocation for the object_t * array, but an additional 20 000 allocations for the names and children of those objects.
This seems a bit wasteful, but computers are really fast, so this approach can work well in many cases. We have a fair number of arrays like this in The Machinery – not for strings (more about that later), but certainly for vectors. The only difference is that instead of using an std::vector we use a stretchy buffer. Why? Well, for one, we program in C rather than C++ so we can’t use STL. But even if we used C++ we might still prefer this approach, because C++ classes can be tricky to use with the bulk data allocation approaches I described in part 1.
First, remember how we stored the objects in an “array with holes” by making the stored data type a union of the original data we wanted to store and a free list pointer for keeping track of the free items:
typedef union { object_t; freelist_item_t; } item_t;
This doesn’t work with std::vector, because objects with non-trivial copy constructors can’t be stored in unions. To make this work with STL objects we either have to use extra memory to store the freelist pointers with the object itself, or use something like std::variant (shudder).
Second, remember our nice trick of just reserving a large chunk of VM memory to hold our bulk data array. This works well with our C data structures, because they are zero-initialized and the memory we get from the VM is always cleared to zero (since otherwise, the VM would leak information between processes). So, with C data structures, we can just use the memory directly, whereas with C++ we would have to placement-new our strings and vectors into the memory.
In other words, in this use case, using the STL data types adds a lot of extra bookkeeping for limited benefits.
As I said above, heap allocation can certainly be “good enough” in a lot of circumstances, but if you want to store a really large number of objects, it has some drawbacks that I’ve already talked about earlier in this series:
Making thousands of small allocations is time-consuming and can waste a substantial amount of memory on fragmentation, allocation headers, etc.
Since the arrays are allocated individually on the heap, they might be far apart in memory, resulting in cache misses when we process the objects.
With lots and lots of small allocations, it is hard to get a good picture of how much memory the system is using and what the access patterns are.
So let’s look at alternatives!
Private heap
One way of avoiding to make lots of small allocations from system memory is to make one big allocation and then chop it up ourselves into smaller pieces. Since we’re allocating a big chunk, we can request it directly from the VM and bypass the system heap allocator completely:
Private heap.
Essentially, what we’re doing here is implementing our own memory allocator. Getting chunks of memory from the VM and chopping them up into chunks to fulfill malloc and new requests is just what a memory allocator does.
Why would we ever want to do this, since we already have a perfectly good system memory allocator?
Well, to begin with, I think it is a really useful exercise. Writing your own memory allocator makes you think about how memory really works — it’s just bytes all the way down, and any “objects” you see are just your own mental projections. It may seem daunting and scary at first, but it’s not as hard as you might think. Try it!
But OK, personal development aside, why would we want to write our own memory allocator? Certainly, the system allocator has been written by “experts” and there is nothing we mere mortals could ever do to improve on it.
Actually, you’d be surprised. It used to be, not too long ago, a lot of systems shipped with really crappy system allocators. By switching out the standard allocator for something like dlmalloc, you could give your game a nice 5-10 % performance boost. (Provided your game did tons of small memory allocations in the update loop, which of course you should not be doing. That’s what this whole series is about, remember?) I think that’s all fixed these days, though, and everything ships with something that is at least comparable to dlmalloc in terms of performance.
But it’s still possible to do better! How? Well, the standard memory allocator has to deal with a lot of different situations. Different applications have different memory patterns and since the standard allocator can never know exactly what’s going to be thrown at it, it has to do something that works kind-of-okay in a lot of different situations. And it’s really hard to write something that works good for everything, so you can usually come up with some adversarial worst-case input that makes the allocator completely crap out and go O(n²).
In contrast, if you are writing an allocator just for your specific application — or even better, for onespecific system in your application — you have a lot more information. Your allocator doesn’t have to work well for any weird data that might be thrown at it, it just has to work well for the allocation patterns of that system. That is a lot simpler, and a lot more well-defined problem to solve. It is also a lot easier to test — you can just feed the allocator the data you expect and see how well it performs. So you can easily check if you manage to do better than the system allocator or not.
Just to convince you further, here are some examples of how you can do better than the system allocator:
A lot of command-line programs just perform a single task and then exit. They tend to allocate a bunch of memory as they are performing the task and then free it all when they exit. These programs may actually run significantly faster with an allocator that just never frees the memory. Memory leaks aren’t really an issue with these programs, since once they exit, all the memory is returned to the system anyway. So doing a lot of bookkeeping in order to reclaim memory is not worth it. If memory is never freed we can use a simple pointer bump allocator to allocate it.
If you’re not writing a generic allocator, you can change the allocator API. For example, you can make your free() function take two arguments — the pointer and the size of the memory block that is being freed. This size should always be known by the owner of the memory block, because if the owner didn’t know the size, how could they use the memory without causing access violations? Forcing the owner to pass the size to free() means that the allocator doesn’t have to remember it, which is nice. For example, suppose someone calls malloc() to allocate 4K of memory. With a 4K page size, malloc() could service this directly from the VM, but where would it store the size of the memory block? Either it has to allocate more memory for a preamble that holds the size, which means that the allocation no longer fits nicely into a system page, or it has to store the size some other way — such as in a hash table. If free() passes the size, malloc() doesn’t have to worry about storing it. We actually use this approach for all memory allocations in The Machinery.
A generic allocator needs to implement synchronization to make sure multiple threads are not allocating memory simultaneously. If you are writing your own allocator for a specific system, synchronization might already be dealt with by that system, at a higher level, which means you don’t have to repeat the effort in the allocator.
So writing your own memory allocator can make things faster. But depending on how simple you are able to make it, there can still be a significant overhead from all those allocations. Also, we haven’t done anything to solve the problem of fragmentation. Allocating and freeing blocks of different sizes will leave holes of different sizes in our memory block, that are hard to reuse.
Can we do better?
Chunked allocator
One way of getting rid of fragmentation is to implement heap compaction. I.e., instead of holding pointers to objects we hold handles that can be resolved into pointers. This allows us to defragment the heap by moving the memory blocks and updating the pointers that the handles resolve to. The main problem with this is that it can be really error prone, since you have to make sure to lock and unlock pointers so they don’t get moved while you are using them.
But there is another way. Fragmentation is caused by allocating and freeing memory blocks of different sizes. This leaves differently sized holes that we have to try to fill with future allocations. If all allocations were the same size we wouldn’t have this problem at all. In fact, in this case, we would just have the same situation as we had in the first part of this series — the bulk data array. We can just keep all the freed blocks in a free list and when the user wants to allocate more memory, we just give her the first block from the free list. Since all the blocks are the same size, the block will be the right size.
Is there a way to make all allocations the same size when all the objects can have a different number of children? Yes. What if we make each allocation a fixed-size “chunk” or “block” of children — say 16 at a time. If an object needs more than 16 children we can just allocate multiple chunks for that object and link them together with pointers.
With this approach, both objects and child_chunks are just bulk data arrays, like the ones we encountered in the first part of this series. To find all the children of an object, we follow its child_chunks pointer to get to the first chunk of children and then follow the next_chunk pointers to get any additional chunks.
How does this solution perform compared to using an std::vector? The main drawback is that we can no longer randomly access objects in constant time with [i], so if you need that, this is not a good solution. Note though, that we can still iterate over all objects in O(n) — same as for the std::vector.
Allocating and freeing a child_chunk_t is very cheap — just a few operations — a lot cheaper than if we were using a generic memory allocator. We can also make use of the tricks we used for the bulk data — such as allocating memory directly from the VM. It is very easy to see how much memory the system is using and what the access patterns are since we only have two allocations that we need to worry about — objects and child_chunks.
We get less memory coherency than we would with an std::vector. Instead of having all items continuous in memory, they are only continuous in chunks of CHILD_CHUNK_SIZE. Whenever we follow the next_chunk pointer we might get a cache miss. Note though that we have some control of this, by using different values for CHILD_CHUNK_SIZE. The higher we set it, the more objects we can process at one time before pointer chasing.
Also note that most of the time, chunks from the same child array will tend to end up next to each other since typically the children will be added at the same time, which means they will be allocated next to each other in memory (unless they’re allocated from the free list). So this might be less of an issue than you think.
In terms of memory, this solution has no external fragmentation — all the “holes” created when we free a child_chunk_t are perfectly sized for the allocation of another child_chunk_t. However, we do have internal fragmentation, since we’re always allocating at least CHILD_CHUNK_SIZE items in every chunk, even if we need less than that. The larger CHILD_CHUNK_SIZE is, the more memory we lose to internal fragmentation. We also have some overhead from the prev_chunk and next_chunk pointers. (We could store them as indices to reduce the overhead.)
How does the memory use compare to std::vector? It’s a bit tricky to say since there are a lot of factors involved. First, will children be added dynamically, so that we need to use push_back() and rely on geometric growth to get amortized constant time for adding elements, or, are all children known in advance so that we can just resize() the vector to the right size? If it’s the former, then the vector will be about 50 % empty on average, which for big vectors will be a lot more than the CHILD_CHUNK_SIZE. Second, the vector will have some amount of external fragmentation as well as overhead from preambles and postambles. But how much this is depends on the implementation details of the allocator and the size of the vector. For example, if the vector is small enough to fit in one of the fixed-size allocation pools of the system allocator, it doesn’t need a preamble and postamble and will not cause external fragmentation.
Personally, the main reason I like this approach over using an std::vector is that it’s transparent. It is easy to see exactly how much memory is being used and where memory is being wasted. We can easily follow the access pattern and see how much pointer-chasing we are doing. This transparency makes it easy to discover and fix any performance issues we run into. For example, we can play with the CHILD_CHUNK_SIZE or even create two different child_chunk arrays with different chunk sizes, to better accommodate both large and small arrays.
In constrast, the system allocator is essentially a black box. Unless you want to do some really deep digging, it’s hard to tell how it works, hard to tell how much memory you are spending on headers and fragmentation. It’s hard to even see if you have a problem, and even harder to fix it, since that means rewriting the system allocator.
I always prefer simple transparent system that can be easily hacked and tweaked over complicated black boxes.
What is a good chunk size for the chunked allocator? If we set it too low then we’re jumping around in memory a lot and also spending a lot of memory overhead on the prev_chunk and next_chunk pointers. If we set it too high, then we’re losing a lot of memory to internal fragmentation.
I think you shouldn’t go smaller than fitting a child_chunk_t in a cache line. If we use 32-bit indices instead of pointers for everything to save space, that means we’re using 4 bytes each for the prev and next references and 4 bytes for every object index. So if we use CHILD_CHUNK_SIZE = 14 each child_chunk_t will be exactly 64 bytes. I don’t think there are many cases where you would want to go >14 elements either. Usually, small arrays are more common than large ones, so a higher number would mean a lot of internal fragmentation:
I.e., the child chunks just turn into a linked list of siblings. In fact, in this case, we don’t really need the child_chunk_t structure at all, we could just let the sibling pointers point directly into the object_t * array and get:
To enumerate all the children of an object stored in this way, we would first follow the first_child pointer to get to its first child and then keep following the next_sibling pointers to enumerate all the siblings of that child.
This solution is almost exactly the same as the one we used in part 2 of this series to find all the observations with a particular observer.
So this gives us another way of storing arrays of arrays. Instead of explicitly representing the children as an array:
Parent
Children
Ewing
[Edith, Phelan, Bouvier]
Bouvier
[Jr, Nicholas, Christopher]
We can represent that data as a relationship, as we would in a relational database:
Parent
Child
Ewing
Edith
Ewing
Phelan
Ewing
Bouvier
Bouvier
Jr
Bouvier
Nicholas
Bouvier
Christopher
and then use the techniques outlined in the previous post to enumerate all the children of a particular parent.
Which approach is best? Using explicit arrays is faster and uses less memory, but it only allows us to search the data one way, from parent to children. If we want to remove a particular child from the child array of its parent, we have to iterate through all the children to find the child we are looking for, which can be expensive if the arrays get large.
In contrast, the relational representation allows us to search using multiple criteria. For example, as we saw in the last post, we can add a child index and then we can search for a particular child and remove it from its parent as an O(1) operation.
I would use the array representation if I didn’t need these more advanced search options, and the relational representation otherwise.
Arrays of strings
So far, I’ve talked a lot about the children array, but I haven’t really said anything about the name string. Well, a string is just an array of characters, right? So we could just use any of the techniques described above for storing arrays of things to store an array of characters, i.e. a string, right?
Wrong! Well, not totally wrong, of course, we could do that, theoretically. But I think that thinking of a string as an “array of characters” is fundamentally misguided. In fact, it’s one of my pet peeves. What matters in data-oriented design is how data is used, and strings are used very differently than other “arrays of things”.
When you think of an std::vector, what are the typical operations that you want to do with it?
Iterate through all the items and call some method on each one:
for (const auto &it = v.begin(); it != v.end(); ++it) f(it);
Add a new item to the vector:
v.push_back(x);
Remove an item from the vector:
std::iter_swap(it, v.end() - 1); v.pop_back();
None of these operations are things you would typically do with a string!
If I have a string "Niklas" in my program, I never want to randomly add or remove characters. "Nklas" and "Niklasz" make no sense. I might iterate over the characters to draw them in the UI, but that’s only at one place in the code. Instead I’m probably more interested in comparing strings for equality (strcmp()) or composing substrings into larger strings (sprintf()). None of these are typical operations for other “arrays of things”.
The primary differences between strings and other arrays are:
By strings being immutable, I simply mean what I said earlier, that we don’t tend to add and remove characters in strings the same way we do with other arrays. Instead, when we change strings, we typically change the whole thing.
For example, imagine we want to change the string:
- last_name = "Frykholm" + last_name = "Gray"
We don’t think of this as removing the letters F, k, h, o, l, m and adding G, a. Rather, we think of this as a single rename operation — changing the whole last name. And that’s how most strings work (we’ll look at some exceptions later).
So strings aren’t really “arrays of characters”, they are names or identifiers. This is why in a lot of cases, you don’t even need to store the string itself, you can just store an uint64_t hash of the string and compare that to check if a name matches. The only time you need to store the string is if you need to show it to a human (debug printing, logging, UI) or pass it to another system (fopen()).
Unless you’re writing a word processor or something like that, I can only think of two cases where you have mutating strings:
When the user is editing a string in a text box.
When you are building a string up from parts — i.e., concatenating substrings into a path, or an error message.
For editing — presumably the user can’t be editing more than one string at a time (in whatever text box has focus), so this is really a special case. You can have a single char array in your program to hold this “currently edited string”. At the start of editing, you copy whatever string the user is editing into this array so that the text box can use it. When editing finishes, you create a new immutable string from the content of the array and then rename the original object to this new string.
Building up a string from parts is a good use case for temporary memory. In The Machinery, we have an sprintf() implementation that uses a temporary memory allocator, rather than a fixed-size buffer, so it can be used to build arbitrarily large strings. Once you are done constructing the string, you either use it (print the debug message, etc) or if you need to save it for later, convert it into an immutable string.
Reused strings can pop up in things like JSON parsing, where the same object key (e.g. "properties") can show up hundreds or thousands of times. Storing a separate copy of the string each time it appears can be really wasteful.
If we treat strings as immutable, we don’t need separate copies, we can just make all the string pointers point to the same data:
Immutable strings.
It doesn’t matter how many "properties" strings we need. Using this technique, we can create as many strings as we like and still have only one copy in memory. Since the string data will never change (strings are immutable), sharing it is fine.
This technique of letting all the strings with the same data share the same pointer is called string interning and it has some interesting consequences. For one, we don’t have to compare strings with strcmp() or hashing anymore. Since we know that identical strings will use the same pointer, we can just compare the const char * pointers. s1 == s2 if and only if the pointers are equal.
Note that some programming languages, such as Lua, use interning for all their strings. Others, such as Ruby and Lisp, have a separate symbol data type which represents an interned string.
To implement string interning in C, I use a big buffer to hold the string data and a hash table to look up strings in the buffer. The buffer can be reserved from virtual memory or allocated using one of the other techniques described in part 1 of this series. The buffer just stores all the strings consecutively and the hash table holds indices or pointers to these strings:
String interning.
The hash table is needed when strings enter the string interning system. For example, suppose you read a string from a file. After you’ve read it, it will be in some temporary memory array char *. To intern this string you need to check if you have a copy of it in your buffer already. If you do, you can just return a pointer to that string. If not, you should allocate a new string at the end of the buffer and return a pointer to that.
Here’s what the code might look like in practice:
// Commit VM memory in 4K chunks. enum {CHUNK = 4 * 1024}; struct string_repository { uint32_t buffer_size; char *buffer; hash32_t lookup; }; const char *intern(struct string_repository *sr, const char *s) { const uint64_t h = murmurhash_string(s); const uint32_t idx = hash32_get(&sr->lookup, h, UINT32_MAX); if (idx < UINT32_MAX) return sr->buffer + idx; // Commit VM memory. (Assumes we're using the VM method for storing // the buffer.) Note: This is only needed on Windows which makes a // distinction between reserving and committing virtual memory. const uint32_t n = (uint32_t)strlen(s); const uint32_t size = sr->buffer_size; const uint32_t new_size = size + n + 1; const uint32_t chunks = div_round_up(sr->buffer_size, CHUNK); const uint32_t new_chunks = div_round_up(new_size, CHUNK); if (new_chunks != chunks) vm->commit(sr->buffer + chunks * CHUNK, (new_chunks - chunks) * CHUNK); // Copy string data into buffer and update hash table memcpy(sr->buffer + sr->buffer_size, s, n + 1); hash32_add(&sr->lookup, h, sr->buffer_size); }
Note that if you want to do tricks like comparing strings by pointers, you have to make sure that both the strings are interned. If one of the strings is a string literal or has just been read from a file into a dynamic buffer, it won’t work. It’s only when strings have entered the interning system that strings with the same value have the same pointer.
When programming languages use string interning, they typically have one single string repository where all the strings in the program go. However, when you’re managing your own string repository I find it more useful to have separate per-system or per-object string repositories. For example, when parsing a JSON file, I would assign it it’s own string repository. This way, when you’re done with the parsing, you can just throw away the whole repository and free the memory.
Note that this again means that you need to be careful. If you try to compare strings by pointers and the strings are not from the same string repository, it won’t work.
So far, we haven’t described any mechanism for removing strings from the string repository. If we want to be able to do that, we first need to add reference counts to the string buffer. Since the same buffer data can be shared by multiple strings, we need to count how many times that happens, so that we can know when the data is no longer used and is safe to be deleted or reused.
Second, when strings are deleted, it will leave holes in our big string buffer:
String buffer holes.
To reuse this memory for other strings we must keep track of where all the holes are. We also probably want a mechanism for merging small neighboring holes into bigger holes, because otherwise, we’ll end up with smaller and smaller holes, that won’t be useful for anything but the shortest strings.
Note that this is exactly the same problem that a heap memory allocator has to solve, and we can address it using the same techniques. For example, we can link holes together in linked lists based on their sizes to make it possible to find them. We can also add preambles and postambles to all string allocations so that we can find neighboring allocations as targets for merging. Note that these preambles and postambles will add some overhead to every allocation. Also, we must round up the allocations to some minimum size, so that we are sure that the linked list pointers will fit in the “hole” that the allocation leaves when we free it.
Of course, we could also make use of all the other little tricks that memory allocators do. For example, we could have “pools” of allocators for strings of fixed sizes, etc, etc. It starts getting complicated.
Another thing you could do is to represent the strings as handles instead of pointers. I.e. you let the intern() function return an uint32_t string ID instead of an actual char * and then you have another function that looks up from the ID to the actual string data. Now, since nobody is pointing directly to the string, you can move the strings in memory and get rid of holes that way. This is the “compacting heap” approach.
In practice, I do it like this: I allocate the strings in blocks of 4 K. For each block, I keep track of how much “string” data and how much “hole” data it contains. When the block is > 50 % empty, I “defragment” the block by packing the strings tightly. The memory that’s left at the end of the block can then be used for new strings.
String buffer defragmentation.
The third option is to not bother with removing strings and reclaiming memory at all. This the absolutely simplest option and in many cases a perfectly valid one. Remember that our typical use case for this is to store object names and it is unlikely that objects will be renamed so much that the memory leaks become a problem. Another use case was for JSON parsing. Here, by using a designated string repository that we throw away at the end of the parse, there is no memory wasted at all. Any system that produced a large number of unique strings, such as logging, wouldn’t use this system anyway, but instead, just use temporary memory for the strings.
Conclusion
Together, the techniques outlined in this series: bulk data arrays, indices and arrays of arrays, cover almost all the data structure needs we have in The Machinery. Is there something that seems to be missing? Tweet me at @niklasfrykholm.
SAN JOSE, Calif. (AP) -- A former Yahoo software engineer has pleaded guilty to hacking into the accounts of some 6,000 Yahoo users in search of sexual photos and videos.
The US Attorney's Office says Reyes Daniel Ruiz admitted in court Monday that he mostly targeted accounts belonging to younger women, including his personal friends and work colleagues.
Prosecutors say once he gained access to Yahoo accounts, he was able to compromise iCloud, Facebook, Gmail and other online services in search of private images.
The 34-year-old stored the material on a private computer that he destroyed after his employer noticed the suspicious activity.
Ruiz, of the Northern California city of Tracy, pleaded guilty to one count of computer intrusion. He faces five years in prison when he's sentenced Feb. 3.
func main() { users := []User{User{"alice"}, User{"bob"}} // hint: this line compiles, User fulfils Named var _ Named = User{"charlie"} getName(users[0]) getNames(users) } func getName(n Named) string { n.name() } func getNames(ns []Named) []string { /* ... */ }
It doesn't compile. Surprisingly, although User implements Named, and the getName call is fine, the getNames(users) call is a type error.
When I first came to Go it confused me that if User implemented Named I wasn't able to use a User wherever I saw a Named in the types of arguments. Instead, although I could pass User to a method accepting Named:
I couldn't pass []User as a []Named
I couldn't pass []User as an []interface{}
I couldn't pass *User as *Named
Here's a fuller example demonstrating all of these cases.
package main import "fmt" func main() { users := []User{User{"alice"}, User{"bob"}} getName(users[0]) // cannot use users (type []User) as type []Named in // argument to getNames getNames(users) // cannot use users (type []User) as type []interface // {} in argument to countSlice countSlice(users) // cannot (type *User) as type *Named in argument // to switchNamed: switchNamed(&users[0], &users[1]) } func getName(n Named) string { return n.name() } func getNames(ns []Named) []string { /* ... */ } func countSlice(ns []interface{}) int { return len(ns) } func switchNamed(a,b *Named) { /* ... */ } type User struct { fullName string } func (u User) name() string { return u.fullName } type Named interface { name() string }
It felt inconsistent. It was also very different from languages like TypeScript and Java, where if User implemented Named, as well as being able to pass User to a method accepting Named:
I could pass User[] as a Named[]
I could pass User[] as an any[] (TypeScript only)
For instance, here's the same example in TypeScript (minus switchNamed as TS doesn't have pointers) which compiles and runs without a hitch:
function main() { const users = [new User("alice"), new User("bob")] console.log( getName(new User("charlie")), getNames(users), countArray(users), ) } class User { constructor(private fullName: string) {} name() { return this.fullName } } interface Named { name(): string } function getName(n: Named) { return n.name() } function getNames(ns: Named[]) { return ns.map(n => n.name()) } function countArray(ns: any[]) { return ns.length }
The mystery I wanted to solve was why Go worked exactly the same way in some places (getName(users[0])), but not in others (getNames and countSlice). To solve it I had to learn how Go's interfaces really worked.
Clearing up the mystery
First, an intuition for the difference between interface values and concrete values in Go. Imaging helping your friend move their pets to a new home. They give you two boxes, one labelled 'friendly snakes', one 'fluffy spiders'. Easy enough, sling both boxes in your car and drive! But does that scenario prove you could do the same if they just handed you the critters unboxed? Not at all.
Equivalently, do not assume that because you can store a concrete Userin a Named interface value, you can use that concrete value as an interface value. A concrete value and an interface value containing it are fundamentally different things and can be used in different ways.
But if that's true, how is logOne able to accept User values? Simple: the Go compiler automatically creates interface values for you where it can. The two lines below are equivalent:
// Go implicitly allocates an interface value and places the User in it logOne(User{"charlie"}) // ...equivalent to us manually allocating one and passing it var f1 Named = User{"charlie"} logOne(f1)
What interface values are really
Let's make it concrete by considering what these 'boxes' look like. Go's interface values are really a pair of pointers. When you put a concrete value into an interface value, one pointer starts pointing at the value. The second will now point to the implementation of the interface for the type of the concrete value. They're called the dynamic value and the dynamic type respectively - dynamic because both are set at runtime when we assign concrete values into an interface value.
This pair of pointers is the secret to how Go's interfaces work. When a method is called on an interface value, Go follows the implementation pointer to find the appropriate method and the value pointer to be able to use the value as the receiver (or it panics if the 'box' is empty: a nil value). Thus you can see why code that works with an interface value really cannot work on concrete values alone.
The slice inconsistency
A check on your understanding: why can't we pass a []User as a []Named? Try to think through what the two slices/backing arrays would look like in memory.
Answer
The crux is again that an interface value is a different thing to a concrete value, rather than - as in other languages - just another way a concrete value can be used. Each cell in an interface value will contain one of those familiar double pointer values:
However, given Go can automatically allocate a Named where required, couldn't Go also allocate a []Named automatically to let you pass a []User to getNames? It's certainly possible to imagine how Go could do it. It could allocate a new slice of interface values for you, and assign the concrete User values into corresponding indexes:
users := []User{User{"alice"}, User{"bob"}} // below is what Go would have to do to make switchItems(users, 0, 1) work implicitly ns := make([]Named, 0, len(users)) for _, u := range users { var n Named = u ns = append(ns, n) // * } getNames(ns)
Indeed, for getNames(users) this would actually work fine! But slices have mutable indexes. and many functions mutate the slices they're passed. Can you see why automatically creating new slices to pass in would not work as desired for such functions? For instance:
func switchItems(xs []Named, a, b int) { t := xs[a] xs[a] = xs[b] xs[b] = t } users := []User{User{"alice"}, User{"bob"}} // not possible, but imagine it was and Go did the implicit // allocate/initialize we did above switchItems(users, 0, 1)
The implicit allocation would stop switchItems from working as we'd only be affecting the newly allocated slice/backing array - ns in the example above where I showed you what Go would have to do to make it work.
Again, Go's helpful implicit conversions can make this confusing - for append(ns, n) we could just do append(ns, u), but now we know Go must be allocating the interface value for us.
Takeaways
If get a type error when you attempt to use a concrete value in a place needing an interface value and you think "but it fulfils the interface", remember: interface values and concretes are very different things. That you can place a concrete value in an interface value does not mean it is an interface value, so you can't use it in all the same ways.
For instance, if you have a function accepting []interface{} you can't pass a slice of concrete values. Although we know all interfaces fulfil the empty interface, an interface value is still different from a concrete value: it's a container which allows us to peek in and extract the concrete type via type assertions. So if we have a slice of concrete values we're going to have to allocate interface values to pass in:
func findAndRemoveUsers(xs []interface{}) { for i, x := range xs { if _, ok := x.(User); ok { fmt.Println("There is a user at", i) xs[i] = nil } } } users := []User{User{"alice"}, User{"charlie"}} // could just as well be []interface{} ivs := make([]Named, 0, len(users)) for _, u := range users { ivs = append(ivs, u) } findAndRemoveUsers(ivs) // double check it's clear to you why this couldn't be // supported automatically - consider xs[i] = nil findAndRemoveUsers(users)
Quiz time
Why couldn't Go do something clever to let us pass a pointer to a User to a method accepting a pointer to Named?
func switchNamed(a,b *Named) { t := *a *a = *b *b = t } u1 := User{"denise"} // type error switchNamed(&u1)
Spoiler
Much like with the slice example above, `switchNamed(&u1)` to work Go would have to automatically allocate an interface value. If it did, and passed that into the function, assignments to that fresh *Named would have no affect on the original *User, and so no visibility outside the function. So instead it's a compile-time type error:
// this compiles fine var f1 Named = User{"alice"} var f2 Named = User{"bob"} fmt.Println(f1, f2) // {"alice", "bob"} switchNamed(&f1, &f2) fmt.Println(f1, f2) // {"bob", "alice"} u1 := User{"charlie"} u2 := User{"denise"} fmt.Println(u1, u2) // {"charlie", "denise"} // this won't compile - 'can't use type *User as *Named' // switchNamed(&u1, &u2) // because if we implicitly generated new *Named values // for the &u1, &u2 passed to the method... var n1 Named = u1 var n2 Named = u2 switchNamed(&n1, &n2) // ....we'd end up with u1 and u2 unaffected! fmt.Println(u1, u2) // {"charlie", "denise"}
Note: pointers to interfaces are fairly rare in practise.
Have you engaged in a “show your work” battle with a student? Have you heard this line: “If I can do it in my head, why do I have to write it out?”
You may be fighting the wrong battle.
Writing Out Lesson Plans
Let’s switch our perspective. Have you ever been forced to write out a lesson plan? Did you grumble to your colleagues that you can teach just fine without typed-out plans? That it’s a huge waste of time?
Then you understand the frustration a student feels when they’re forced to write out “the work” for a problem they already know the answer to. For a student who immediately sees that, given 3x = 9, x equals 3, writing out their work is as silly as demanding a 4th grader “prove” that 1 + 1 = 2.
Let’s get it straight, though; a first-year teacher will benefit from writing out lesson plans until they’ve developed mastery, just as a student first learning algebra may need to write out their work to get the solution.
The Solution: Increase Complexity
Forcing students to write out unnecessary work is a fruitless endeavor. It masks the real problem, which is this:
If a student can do it in their heads, then the work is too easy!
Instead of battling over “showing work,” simply increase the complexity of the problem until the student must do the work out to get it right.
If students can “see” the solution to 3x = 9, first congratulate them on having such an intuitive mathematical mind. Then, differentiate the problem until you’re actually challenging the child. Have your student solve for x given 3x – 2 = 7. This two-step problem may be complex enough to make it useful to show one’s work.
Are your primary students refusing to write out the steps to solve 21+ 30? Increase the complexity to 35 + 21 + 30. Can they do that in their head? Congratulate them (because it is impressive) and then push the complexity another step until the work serves a useful purpose to the student.
This is the crux. Once a student believes in the usefulness of writing out the steps, then they have an incentive (beyond avoiding a nagging teacher) to do so.
As adults, we know that it’s sometimes useful to write out our work because we’ve goofed up enough times while balancing checkbooks. But as teachers, we also know that writing out detailed lesson plans is useful in certain situations.
More On Increasing Complexity
I wrote more about increasing complexity here. We must be careful not to admonish our intuitive learners for being intuitive. As teachers of the gifted, we must set up learning environments that our best for our students. And if they’re doing it all in their heads (and getting it right!), then the environment needs to change, not the student.
