Mike Hommey: When the memory allocator works against you, part 2
This is a followup to the When the memory allocator works against you post from a few days ago. You may want to read that one first if you haven t, and come back. In case you don t or didn t read it, it was all about memory consumption during a 
(Note that in the graph above and the graphs that follow, the horizontal axis represents the number of allocator function calls performed)
While I was here, I figured I d check how mozjemalloc performs, and it has a better behavior (although it has more overhead).
What doesn t appear on this graph, though, is that mozjemalloc also tells the OS to drop some pages even if it keeps them mapped (
(It looks like it has better memory usage than mozjemalloc for this use case, but its stats are being thrown off at some point, I ll have to investigate)
Going back to the first graph, let s get a closer look at what the allocations look like when the system bytes number is increasing a lot. The highlights in the following graphs indicate the range the next graph will be showing.
So what we have here is a bunch of small allocations (small enough that they don t seem to move the requested line ; most under 512 bytes, so under normal circumstances, they would be allocated by python, a few between 512 and 2048 bytes), and a few large allocations, one of which triggers a bump in memory use.
What can appear weird at first glance is that we have a large allocation not requiring more system memory, later followed by a smaller one that does. What the allocations actually look like is the following:
(Note this hasn t actually landed on the
git clone of the mozilla-central mercurial repository using git-cinnabar, and how the glibc memory allocator is using more than one would expect. This post is going to explore how/why it s happening.
I happen to have written a basic memory allocation logger for Firefox, so I used it to log all the allocations happening during a git clone exhibiting the runaway memory increase behavior (using a python that doesn t use its own allocator for small allocations).
The result was a 6.5 GB log file (compressed with zstd ; 125 GB uncompressed!) with 2.7 billion calls to malloc, calloc, free, and realloc, recorded across (mostly) 2 processes (the python git-remote-hg process and the native git-cinnabar-helper process ; there are other short-lived processes involved, but they do less than 5000 calls in total).
The vast majority of those 2.7 billion calls is done by the python git-remote-hg process: 2.34 billion calls. We ll only focus on this process.
Replaying those 2.34 billion calls with a program that reads the log allowed to reproduce the runaway memory increase behavior to some extent. I went an extra mile and modified glibc s realloc code in memory so it doesn t call memcpy, to make things faster. I also ran under setarch x86_64 -R to disable ASLR for reproducible results (two consecutive runs return the exact same numbers, which doesn t happen with ASLR enabled).
I also modified the program to report the number of live allocations (allocations that haven t been freed yet), and the cumulated size of the actually requested allocations (that is, the sum of all the sizes given to malloc, calloc, and realloc calls for live allocations, as opposed to what the memory allocator really allocated, which can be more, per malloc_usable_size).
RSS was not tracked because the allocations are never filled to make things faster, such that pages for large allocations are never dirty, and RSS doesn t grow as much because of that.
Full disclosure: it turns out the system bytes and in-use bytes numbers I had been collecting in the previous post were smaller than what they should have been, and were excluding memory that the glibc memory allocator would have mmap()ed. That however doesn t affect the trends that had been witnessed. The data below is corrected.
(Note that in the graph above and the graphs that follow, the horizontal axis represents the number of allocator function calls performed)
While I was here, I figured I d check how mozjemalloc performs, and it has a better behavior (although it has more overhead).
What doesn t appear on this graph, though, is that mozjemalloc also tells the OS to drop some pages even if it keeps them mapped (madvise(MADV_DONTNEED)), so in practice, it is possible the actual RSS decreases too.
And jemalloc 4.5:
(It looks like it has better memory usage than mozjemalloc for this use case, but its stats are being thrown off at some point, I ll have to investigate)
Going back to the first graph, let s get a closer look at what the allocations look like when the system bytes number is increasing a lot. The highlights in the following graphs indicate the range the next graph will be showing.
So what we have here is a bunch of small allocations (small enough that they don t seem to move the requested line ; most under 512 bytes, so under normal circumstances, they would be allocated by python, a few between 512 and 2048 bytes), and a few large allocations, one of which triggers a bump in memory use.
What can appear weird at first glance is that we have a large allocation not requiring more system memory, later followed by a smaller one that does. What the allocations actually look like is the following:
As it turns out, inspecting all the live allocations at that point, while there was a hole large enough to do the first two reallocs (the second actually happens in place), at the point of the third one, there wasn t a large enough hole to fit 8.8MB. What inspecting the live allocations also reveals, is that there is a large number of large holes between all the allocated memory ranges, presumably coming from previous similar patterns. There are, in fact, 91 holes larger than 1MB, 24 of which are larger than 8MB. It s the accumulation of those holes that can t be used to fulfil larger allocations that makes the memory use explode. And there aren t enough small allocations happening to fill those holes. In fact, the global trend is for less and less memory to be allocated, so, smaller holes are also being poked all the time. Really, it s all a straightforward case of memory fragmentation. The reason it tends not to happen with jemalloc is that jemalloc groups allocations by sizes, which the glibc allocator doesn t seem to be doing. The following is how we got a hole that couldn t fit the 8.8MB allocation in the first place:void *ptr0 = malloc(4850928); // #1391340418 void *ptr1 = realloc(some_old_ptr, 8000835); // #1391340419 free(ptr0); // #1391340420 ptr1 = realloc(ptr1, 8000925); // #1391340421 /* ... */ void *ptrn = malloc(879931); // #1391340465 ptr1 = realloc(ptr1, 8880819); // #1391340466 free(ptrn); // #1391340467
All would go well ifptr1 = realloc(ptr1, 8880467); // #1391324989; ptr1 is 0x5555de145600 /* ... */ void *ptrx = malloc(232); // #1391325001; ptrx is 0x5555de9bd760 ; that is 13 bytes after the end of ptr1. /* ... */ free(ptr1); // #1391325728; this leaves a hole of 8880480 bytes at 0x5555de145600.
ptrx was free()d, but it looks like it s long-lived. At least, it s still allocated by the time we reach the allocator call #1391340466. And since the hole is 339 bytes too short for the requested allocation, the allocator has no other choice than request more memory to the system.
What s bothering, though, is that the allocator chose to allocate ptrx in the space following ptr1, when it allocated similarly sized buffers after allocating ptr1 and before allocating ptrx in completely different places, and while there are plenty of holes in the allocated memory where it could fit.
Interestingly enough, ptrx is a 232 bytes allocation, which means under normal circumstances, python itself would be allocating it. In all likeliness, when the python allocator is enabled, it s allocations larger than 512 bytes that become obstacles to the larger allocations. Another possibility is that the 256KB fragments that the python allocator itself allocates to hold its own allocations become the obstacles (my original hypothesis). I think the former is more likely, though, putting back the blame entirely on glibc s shoulders.
Now, it looks like the allocation pattern we have here is suboptimal, so I re-ran a git clone under a debugger to catch when a realloc() for 8880819 bytes happens (the size is peculiar enough that it only happened once in the allocation log). But doing that with a conditional breakpoint is just too slow, so I injected a realloc wrapper with LD_PRELOAD that sends a SIGTRAP signal to the process, so that an attached debugger can catch it.
Thanks to the support for python in gdb, it was then posible to pinpoint the exact python instructions that made the realloc() call (it didn t come as a surprise ; in fact, that was one of the places I had in mind, but I wanted definite proof):
What happens here is that we re creating a mercurial manifest we got from the server in patch form against a previous manifest. Sonew = '' end = 0 # ... for diff in RevDiff(rev_patch): new += data[end:diff.start] new += diff.text_data end = diff.end # ... new += data[end:]
data contains the original manifest, and rev_patch the patch. The patch essentially contains instructions of the form replace n bytes at offset o with the content c .
The code here just does that in the most straightforward way, implementation-wise, but also, it turns out, possibly the worst way.
So let s unroll this loop over a couple iterations:
This allocates an emptynew = ''
str object. In fact, this doesn t actually allocate anything, and only creates a pointer to an interned representation of an empty string.
This is where things start to get awful.new += data[0:diff.start]
data is a str, so data[0:diff.start] creates a new, separate, str for the substring. One allocation, one copy.
Then appends it to new. Fortunately, CPython is smart enough, and just assigns data[0:diff.start] to new. This can easily be verified with the CPython REPL:
(and this is not happening because the example string is small here ; it also happens with larger strings, like>>> foo = '' >>> bar = 'bar' >>> foo += bar >>> foo is bar True
'bar' * 42000)
Back to our loop:
Now,new += diff.text_data
new is realloc()ated to have the right size to fit the appended text in it, and the contents of diff.text_data is copied. One realloc, one copy.
Let s go for a second iteration:
Here again, we re doing an allocation for the substring, and one copy. Thennew += data[diff.end:new_diff.start]
new is realloc()ated again to append the substring, which is an additional copy.
new += new_diff.text_data
new is realloc()ated yet again to append the contents of new_diff.text_data.
We now finish with:
which, again creates a substring from thenew += data[new_diff.end:]
data, and then proceeds to realloc()ate new one freaking more time.
That s a lot of malloc()s and realloc()s to be doing
- It is possible to limit the number of
realloc()s by usingnew = bytearray()instead ofnew = ''. I haven t looked in the CPython code what the growth strategy is, but, for example, appending a 4KB string to a 500KBbytearraymakes it grow to 600KB instead of 504KB, like what happens when usingstr. - It is possible to avoid
realloc()s completely by preallocating the right size for thebytearray(withbytearray(size)), but that requires looping over the patch once first to know the new size, or using an estimate (the new manifest can t be larger than the size of the previous manifest + the size of the patch) and truncating later (although I m not sure it s possible to truncate abytearraywithout arealloc()). As a downside, this initializes the buffer with null bytes, which is a waste of time. - Another possibility is to reuse
bytearrays previously allocated for previous manifests. - Yet another possibility is to accumulate the strings to append and use
''.join(). CPython is smart enough to create a single allocation for the total size in that case. That would be the most convenient solution, but see below. - It is possible to avoid the intermediate allocations and copies for substrings from the original manifest by using
memoryview. - Unfortunately, you can t use
''.join()on a list ofmemoryviews before Python 3.4.
git clone of mozilla-central looks like the following (with the python allocator enabled):
(Note this hasn t actually landed on the master branch yet)
Compared to what it looked like before, this is largely better. But that s not the only difference: the clone was also about 1000 seconds faster. That s more than 15 minutes! But that s not all so surprising when you know the volumes of data handled here. More insight about this coming in an upcoming post.
But while the changes outlined above make the glibc allocator behavior less likely to happen, it doesn t totally obliviate it. In fact, it seems it is still happening by the end of the manifest import phase. We re still allocating increasingly large temporary buffers because the size of the imported manifests grows larger and larger, and every one of them is the result of patching a previous one.
The only way to avoid those large allocations creating holes would be to avoid doing them in the first place. My first attempt at doing that, keeping manifests as lists of lines instead of raw buffers, worked, but was terribly slow. So slow, in fact, that I had to stop a clone early and estimated the process would likely have taken a couple days. Iterating over multiple generators at the same time, a lot, kills performance, apparently. I ll have to try with significantly less of that.
Apologies the first blog post got sent out by mistake.
Weather comparisons between the two countries
Last year, I had come to know that this year s debconf is happening in Canada, a cold country. Hence, few weeks/month back, I started trying to find information online when I stumbled across few discussion boards where people were discussing about Innerwear and Outerwear and I couldn t understand what that was all about. Then somehow stumbled across this Video, which is of a game called the Long Dark and just seeing couple of episodes it became pretty clear to me why the people there were obsessing with getting the right clothes and everything about it. Couple of Debconf people were talking about the weather in Montreal, and surprise, surprise it was 
Population Density
As well in the game and whatever I could find on the web, Canada seems to be on the lower side as far as population is concerned. 
Rail
This is one thing that is similar in both the great countries. India has Indian Railways and while the Canadians have their own mountain railway called 
Business houses, Political Families
This is again something that is similar in both the countries, it seems (from afar) that its only few business houses and more importantly political families which have governed for years. From what little I could understand, both India and Canada have first past the post system which as shared by its critics is unfair to new and small parties. It would be interesting to see if Canada does a re-think. For India, it would need a massive public education outreach policy and implementation. We just had elections in 5 states of India with U.P. (with respect to area-size and population density) and from the last several years, the EVM s (Electronic Voting Machines) tries to make sure that nobody could know which area which party got the most votes. This is to make sure the winning party is not able to take revenge on people or areas which did not vote for them. Instead you have general region counting of votes with probably even the Election Commission not knowing which EVM went to what area and what results are there in sort of double-blind methodology.
As far as Business houses are concerned, I am guessing it s the same world-over, only certain people hold the wealth while majority of us are in hard-working, non-wealthy status.
Northern Lights, Aurora Borealis
Apart from all the social activities that Montreal is famous for, somebody told/shared with me that it is possible to see the Northern Lights, Aurora Borealis can be seen in Canada. I dunno how true or not it is, while probably in Montreal it isn t possible to see due to light pollution, but maybe around 40-50 kms. from the city ? Can people see it from Canada ? IF yes, how far would you have to go ? Are there any companies or people who take people to see the Northern Lights.
While I still have to apply for bursary, and if that gets ok, then try getting the visa, but if that goes through, apart from debconf and social activities happening in and around Montreal, Museums, Music etc. , this would be something I would like to experience if it s possible. While I certainly would have to be prepared for the cold that would be, if it s possible, no offence to debconf or anybody else but it probably would be the highlight of the entire trip if its possible. This should be called/labelled as the greatest show on earth TM. 
The above picture is the blend of the two communities from foss community and mozilla India. And unless you were there you wouldn t know who is from which community which is what FOSS is all about. But as always I m getting a bit ahead of myself.
Akshat, who works at NCRA as a programmer, the standing guy on the left shared with me in January this year that this year too, we should have two stalls, foss community and mozilla India stalls next to each other. While we had the banners, we were missing stickers and flyers. Funds were and are always an issue and this year too, it would have been emptier if we didn t get some money saved from last year minidebconf 2016 that we had in Mumbai. Our major expenses included printing stickers, stationery and flyers which came to around INR 5000/- and couple of LCD TV monitors which came for around INR 2k/- as rent. All the labour was voluntary in nature, but both me and Akshat easily spending upto 100 hours before the event. Next year, we want to raise to around INR 10-15k so we can buy 1 or 2 LCD monitors and we don t have to think for funds for next couple of years. How will we do that I have no idea atm.
Me and Akshat did all the printing and stationery runs and hence had not been using my lappy for about 3-4 days.
Come to the evening before the event and the laptop would not start. Coincidentally, or not few months or even last at last year s Debconf people had commented on IBM/Lenovo s obsession with proprietary power cords and adaptors. I hadn t given it much thought but when I got no power even after putting it on AC power for 3-4 hours, I looked up on the web and saw that the power cord and power adaptors were all different even in T440 and even that under existing models. In fact I couldn t find mine hence sharing it via pictures below.
I knew/suspected that thinkpads would be rare where I was going, it would be rarer still to find the exact power cord and I was unsure whether it was the power cord at fault or adaptor or whatever goes for SMPS in laptop or memory or motherboard/CPU itself. I did look up the documentation at support.lenovo.com and was surprised at the extensive documentation that Lenovo has for remote troubleshooting.
I did the usual take out the battery, put it back in, twiddle with the little hole in the bottom of the laptop, trying to switch on without the battery on AC mains, trying to switch on with battery power only but nothing worked. Couple of hours had gone by and with a resigned thought went to bed, convincing myself that anyways it s good I am not taking the lappy as it is extra-dusty there and who needs a dead laptop anyways.
Update After the event was over, I did contact Lenovo support and within a week, with one visit from a service engineer, he was able to identify that it was a faulty cable which was at fault and not the the other things which I was afraid of. Another week gone by and lenovo replaced the cable. Going by service standards that I have seen of other companies, Lenovo deserves a gold star here for the prompt service they provided. I probably would end up subscribing to their extended 2-year warranty service when my existing 3 year warranty is about to be over.
Next day, woke up early morning, two students from COEP hostel were volunteering and we made our way to NCRA, Pune University Campus. Ironically, though we were under the impression that we would be the late arrivals, it turned out we were the early birds. 5-10 minutes passed by and soon enough we were joined by 
Our find for the event was Aarti Kashyap who you can see above. She is a third-year student at COEP and one of the rare people who chose to interact with hardware rather than software. From last several years, we had been trying, successfully and unsuccessfully to get more Indian women and girls interested into technology. It is a vicious circle as till a girl/woman doesn t volunteer we are unable to share our knowledge to the extent we can which leads them to not have much interest in FOSS or even technology in general.
While there are groups are 
What had been interesting about the whole journey were the new people who were bringing all their passion and creativity to the fore. From the mozilla community, we had Akshay who is supposed to be a wizard on graphics, animation, editing anything to do with the visual medium. He shared some of the work he had done and also shared a bit about how blender works with people who wanted to learn about that.
Mayur, whom you see in the picture pointing out something about FOSS and this was the culture that we strove to have. I know and love and hate the browser but haven t been able to fathom the recklessness that Mozilla has been doing the last few years, which has just been having one mis-adventure after another.
For instance, 
Like 
These days, most large FLOSS communities have a "Code of Conduct"; a
document that outlines the acceptable (and possibly not acceptable)
behaviour that contributors to the community should or should not
exhibit. By writing such a document, a community can arm itself more
strongly in the fight against trolls, harassment, and other forms of
antisocial behaviour that is rampant on the anonymous medium that the
Internet still is.
Writing a good code of conduct is no easy matter, however. I should know
-- I've been involved in such a process twice; once for
If you write a list of things not to do, then by implication (because
you didn't mention them), the things in the gray area are okay. This is
especially problematic when it comes to things that are borderline
blacklisted behaviour (or that should be blacklisted but aren't, because
your list is incomplete -- see above). In such a situation, you're
dealing with people who are jerks but can argue about it because your
definition of jerk didn't cover teir behaviour. Because they're jerks,
you can be sure they'll do everything in their power to waste your time
about it, rather than improving their behaviour.
In contrast, if you write a list of things that you want people to do,
then by implication (because you didn't mention it), the things in the
gray area are not okay. If someone slips and does something in that
gray area anyway, then that probably means they're doing something
borderline not-whitelisted, which would be mildly annoying but doesn't
make them jerks. If you point that out to them, they might go "oh,
right, didn't think of it that way, sorry, will aspire to be better next
time". Additionally, the actual jerks and trolls will have been given
less tools to argue about borderline violations (because the border of
your code of conduct is far, far away from jerky behaviour), so less
time is wasted for those of your community who have to police it (yay!).
In theory, the result of a whitelist is a community of people who aspire
to be nice people, rather than a community of people who simply aspire
to be "not jerks". I know which kind of community I prefer.
Consulting for Valve in my spare time
I ve been playing in a 5e campaign for around two months now. In the
past ten days or so I ve been reading various source books and
Internet threads regarding the design of 5th edition. I d like to
draw some comparisons and contrasts between 5th edition, and the 3rd
edition family of games (DnD 3.5e and Paizo s Pathfinder, which may be
thought of as 3.75e).
The first thing I d like to discuss is that wizards and clerics are no
longer 
Weblate is growing quite well in last months, but sometimes it's development is really driven by people who complain instead of following some roadmap with higher goals. I think it's time to change it at least a little bit. In order to get broader feedback I've sent out short survey to active project owners in 
But the most important part for me was where users want to see improvements. This somehow matches my expectation that we really should improve the user interface.
We have quite a lot features, which are really hidden in the user interface. Also interface for some of the features is far from being intuitive. This all probably comes from the fact that we really don't have anybody experienced with creating user interfaces right now. It's time to find somebody who will help us. In case you are able to help or know somebody who might be interested in helping, please 
(Note, those memory sizes are RSS, minus shared )
It also was taking an unexpected long time, but then, I hadn t cloned a large repository like mozilla-central from scratch in a while, so I wasn t sure if it was just related to its recent growth in size or otherwise. So I collected data on 0.4.0 as well.
Less time spent, less memory usage ok. There s definitely something wrong on master. But wait a minute, that slope from ~2GB to ~4GB on the git-remote-hg process doesn t actually make any kind of sense. I mean, I d understand it if it were starting and finishing with the Import manifest phase, but it starts in the middle of it, and ends long before it finishes. WTH?
First things first, since RSS can be a variety of things, I checked 
There are two things of note on this data:
Aha! I thought. That definitely looks much better. Less gap between what glibc says it requested from the system and the RSS size. And, more importantly, no runaway increase of memory usage in the middle of nowhere.
I was preparing myself to write a post about how mixing allocators could have unintended consequences. As a comparison point, I went ahead and ran another test, with the 
Heh. It turns out glibc was acting up all alone. So much for my (plausible) theory. (I still think mixing allocators can have unintended consequences.)
(Note, however, that the reason why the python allocator exists is valid: without it, the overall clone took almost 10 more minutes)
And since I had been getting all this data with 0.4.0, I gathered new data without the python allocator with the master branch.
This paints a rather different picture than the original data on that branch, with much less memory use regression than one would think. In fact, there isn t much difference, except for the spike at the end, which got worse, and some of the noise during the Import manifests phase that got bigger, implying larger amounts of temporary memory used. The latter may contribute to the allocation patterns that throw glibc s memory allocator off.
It turns out tracking memory usage in python 2.7 is rather painful, and not all the tools paint a complete picture of it. I hear python 3.x is somewhat better in that regard, and I hope it s true, but at the moment, I m stuck with 2.7. The most reliable tool I ve used here, it turns out, is 
I've written parts of this story in the past, but never in one place
and never in much detail. So why not now?
In 1982 my family moved house, so one morning I went to school and
at lunch-time I had to walk home to a completely different house.
We moved sometime towards the end of the year, and ended up spending
lots of money replacing the windows of the new place. For people
in York I was born in Farrar Street, Y010 3BY, and we moved to a place on Thief Lane, YO1 3HS. Being named as it was I "ironically" stole at least two street-signs and hung them on my bedroom wall. I suspect my parents were disappointed.
Anyway the net result of this relocation, and the extra repairs meant
that my sisters and I had a joint Christmas present that year, a ZX Spectrum 48k.
I tried to find pictures of what we received but unfortunately the web doesn't remember the precise bundle. All together though we received:
