Daniel Lemire's blog

The U.S. Food and Drug Administration (FDA) has approved a clinical trial for “an anti-aging pill”. The pill is simply metformin. Metformin is a cheap drug that is safe and effective to treat type 2 diabetes, an old-age disease. While it has been a part of modern medicine for a few decades, Metformin actually comes from the French lilac, a plant used in medicine for centuries.

The study is called TAME for “Taming Aging With Metformin” or MILES for “Metformin in Longevity Study”. The trial has been driven by Nir Barzilai, a reputed professor of medicine.

What does it mean?

• As far as I can tell, this is the first time the FDA allowed trials to treat aging as a medical condition. The people who will participate are not “sick” per se, they are just “old” and likely at risk to be soon sick because of aging. How this was approved by the bureaucrats of the FDA is beyond me.
• You probably know people who take metformin. You probably don’t know anyone who is 120. So chances are that this clinical trial will not show that metformin can add decades to your life. However, it was observed that people who have diabetes and take metformin can live longer than otherwise healthy people who do not take metformin. Moreover, mice who take metformin live longer. So it is likely that metformin will have a small positive effect. The gain could be just a few extra months or weeks of health. Note that it is not expected that metformin would extend life by preventing death while letting aging continue. It is likely that if metformin has any effect at all, it will be by delaying diseases of old age.
• Did I mention that metformin is cheap and safe? That means that if it works, it will be instantly available to everyone on the planet. Indeed, it is cheap enough to be affordable even in developing countries. (TAME is funded by a non-profit, the American Federation for Aging Research.)

If successful, this trial would have shocking implications. It is widely believed that aging is unavoidable and untreatable. Maybe you can lose weight and put on some cream to cover your wrinkles, but that’s about it. However, if it were shown that a cheap drug costing pennies a day (literally!) could delay the diseases of old age even just by a tiny bit… It would force people to rethink their assumptions.

Will it work? We shall know in a few years.

(For the record, I am not taking metformin nor am I planning to take any in the near future.)

Further reading: Description of the clinical trial: Metformin in Longevity Study (currently recruiting).

When I took Physics courses in college, I learned about how astronauts should age a tiny bit slower than us. Of course, they would be exposed to a lot more radiation so they might develop more cancers. But all in all, I would have been excited about the prospect of living in space.

Then the astronauts came back and we saw them being barely able to walk. Yet these were young men selected among thousands for their physical fitness. That was explained away by saying that the lack of gravity meant a lack of exercise. All these astronauts needed was a good workout. And future astronauts would have a “space gym” so it would all be alright.

But then more results started coming back. Not only do astronauts come back with weak muscles and frail bones… But they also suffer from skin thinning, atherosclerosis (stiffer arteries), resistance to insulin and they suffer from loss of vision due to cataracts many years earlier than expected given their chronological age. These symptoms look a lot like skin aging, cardiovascular aging, age-related diabetes and so forth. In fact, it is pretty accurate to say that astronauts age at an accelerated rate. This is despite the fact that the current generation of astronauts follows a rigorous exercise program. They are also followed medically more closely than just about anyone on Earth: they don’t indulge in regular fast food.

Trudel, one of the leading researchers on this front appears to think that lack of sufficiently strenuous exercise is the problem. He observed that resting greatly accelerates aging:

“(…) after 60 days of bed rest, the marrow of the patients studied looked as if it had aged and grown by four years” (motherboard)

When not attributed to a lack of sufficient exercise, many of these effects seem to be attributed to an increased exposure to radiation. Indeed, astronauts in the International Space Station are exposed to about ten times as much ambient radiation as the rest of us. However, there is only so much you can explain away with a slight increase in radiations. For example, people exposed to radiation grow cancers, they don’t develop diabetes. And even cancer is not a given: a small increase in radiation exposure can actually make you healthier through a process called hormesis. In fact, that’s precisely what exercise does: it is a stress on your body that makes you healthier. In any case, we do not know whether astronauts are more likely to die from cancer. Certainly, they don’t all fall dead at 40 from cancer… If there is an increased rate of cancer, it is fairly modest because, otherwise, we would not be worrying about how their skin is getting thinner.

So it looks like despite short stays, and very attentive medical care, astronauts age at a drastically accelerated pace… not just in one or two ways but across a broad spectrum of symptoms.

I looked as hard as I could and I could not find any trace of medical scientists worrying about such a phenomenon a priori.

What is going on? Why does life in space accelerate aging so much?

Further reading:

• Thompson, Richard E., et al. Case-control study of lung cancer risk from residential radon exposure in Worcester County, Massachusetts. Health physics, 2008.
• Waterloo to lead new experiment aboard International Space Station, 2015.
• Rainer Facius, No Evidence for the Causation by Cosmic Radiation of Nuclear Cataracts in Pilots, Arch Ophthalmol. 2006.
• Matthew Stock, Astronauts’ skin gets thinner in space, 2015.
• Calla Cofield, For Astro Mice, Skin Ages Faster in Space, 2015.
• Ben Richmond, Life in Space Can Make Your Body Age Faster, 2013
• Versari et al., The challenging environment on board the International Space Station affects endothelial cell function by triggering oxidative stress through thioredoxin interacting protein overexpression, FASEB 2013.

As we work at something, we usually get better and better. Then you hit a plateau. For most of human history, people have been hitting this plateau, and they just kept working until death or retirement, whichever came first.

Today, if you ever reach the upper bound, chances are good that you should be moving to new work.

I do think, for example, that we should be investing more every year in health, education and research. And not just a bit more. However, these people have to do their part and grow their productivity.

If you have been teaching kids for ten years, on the same budget, and getting the same results… you have been short-changing all of us.

If you are treating medical conditions for the same cost and getting the same results for the last few years, you are stealing from all of us.

You have an obligation to improve your productivity with each passing year. And only if all of us keep on improving our productivity can we afford to grow everyone’s budget year after year.

If your students’ scores don’t improve year after year, if the survival rates of your patients don’t improve year after year, you should be troubled. And, ultimately, you should feel shame.

Ten years ago, a team lead by Irina Conboy at the University of California at Berkeley showed something remarkable in a Nature paper: if you take old cells and put them in a young environment, you effectively rejuvenate them. This is remarkable work that was cited hundreds of times.

Their work shows that vampire stories have a grain of truth in them. It seems that old people could be made young again by using the blood of the young. But unlike vampire stories, this is serious science.

So whatever happened to this work? It was cited and it lead to further academic research… There were a few press releases over the years…

But, on the whole, not much happened. Why?

One explanation could be that the findings were bogus. Yet they appear to be remarkably robust.

The theory behind the effect also appears reasonable. Our bodies are made of cells, and these cells are constantly being reconstructed and replenished. As you age, this process slows down.

Some scientists believe that the process slows down to protect us from further harm. It is like driving an old car: you do not want to push it too hard so you drive ever more slowly as the car gets older. Others (like Conboy I suspect) appear to believe that it is the slowing down of the repair itself that causes ill-health as we age.

But whatever your favorite theory is… what Conboy et al. showed is that you could re-activate the repair mechanisms by fooling the cells into thinking that they are in a young body. At the very least, this should lead to an increased metabolism… with the worst case scenario being a much higher rate of cancer and related diseases… and the best case being a reversal of aging.

We have some elegant proof of principles, like the fact that oxytocin appears to rejuvenate old muscles so that they become seemingly indistinguishable from young muscles. (You can order oxytocin on Amazon.com.)

So why did we not see much progress in the last ten years? Conboy et al. have produced their own answer regarding this lack of practical progress:

If all this has been known for 10 years, why is there still no therapeutics?

One reason is that instead of reporting broad rejuvenation of aging in three germ layer derivatives, muscle, liver, and brain by the systemic milieu, the impact of the study published in 2005 became narrower. The review and editorial process forced the removal of the neurogenesis data from the original manuscript. Originally, some neurogenesis data were included in the manuscript but, while the findings were solid, it would require months to years to address the reviewer’s comments, and the brain data were removed from the 2005 paper as an editorial compromise. (…)

Another reason for the slow pace in developing therapies to broadly combat age-related tissue degenerative pathologies is that defined strategies (…) have been very difficult to publish in high impact journals; (…)

If you have not been subject to peer review, it might be hard to understand how peer comments can slow down researchers so much… and even discourage entire lines of research. To better understand the process… imagine that you have to convince four strangers of some result… and the burden is entirely on you to convince them… and if only just one of them refuses to accept your argument, for whatever reason, he may easily convince an editor to reject your work… The adversarial referee does not even have to admit he does not believe your result, he can simply say benign things like “they need to run larger or more complicated experiments”. In one project I did, one referee asked us to redo all the experiments in a more realistic setting. So we did. Then he complained that they were not extensive enough. We extended them. By that time I had invested months of research on purely mundane tasks like setting up servers and writing data management software… then the referee asked for a 100x extension of the data sizes… which would have implied a complete overhaul of all our work. I wrote a fifteen-page rebuttal arguing that no other work had been subjected to such levels of scrutiny in the recent past, and the editor ended up agreeing with us.

Your best strategy in such case might be to simply “give up” and focus on producing “uncontroversial” results. So there are research projects that neither I nor many other researchers will touch…

I was reminded of what a great computer scientist, Edsger Dijkstra, wrote on this topic:

Not only does the mechanism of peer review fail to protect us from disasters, in a certain way it guarantees mediocrity (…) At the time, it is done, truly original work—which, in the scientific establishment, is as welcome as unwanted baby (…)

Dijkstra was a prototypical blogger: he wrote papers that he shared with his friends. Why can’t Conboy et al. do the same thing and “become independent” of peer review? Because they fear that people would dismiss their work as being “fringe” research with no credibility. They would not be funded. Without funding, they would quickly lose their laboratory, and so forth.

In any case, the Conboy et al. story reminds us that seemingly innocent cultural games, like peer review, can have a deep impact on what gets researched and how much progress we make over time. Ultimately, we have to allocate finite resources, if only the time of our trained researchers. How we do it matters very much.

Thankfully, since Conboy et al. published their 2005, the world of academic publishing has changed. Of course, the underlying culture can only change so much, people are still tailoring their work so that it will get accepted in prestigious venues… even if it makes said work much less important and interesting… But I also think that the culture is being transformed. Initiatives like the Public Library of Science (PLoS) launched in 2003 have showed the world that you could produce high impact serious work without going through an elitist venue.

I think that, ultimately, it is the spirit of open source that is gaining ground. That’s where the true meaning of science thrived: it does not matter who you are, what matters is whether you are proposing works. Good science is good science no matter what the publishing venue is… And there is more to science than publishing papers… Increasingly, researchers share their data and software… instead of trying to improve your impact through prestige, you can improve your impact by making life easier for people who want to use your work.

The evolution of how we research may end up accelerating research itself…

Life has a way to give me what I want. Back in 2009, I wrote that instead of following conferences or journals, I would rather follow individual researchers. At the time, there was simply no good way to do this, other than visiting constantly the web page of a particular researcher. A few years later, Google Scholar offered “author profiles” where you can subscribe to your favorite researchers and get an email when they publish new work. Whenever I encounter someone who does nice work, I make sure to subscribe to their Google profile.

This week, I got another of my wishes granted.

Unsurprisingly, most academics these days swear by Google Scholar. It is the single best search engine for research papers. It has multiplied my productivity when doing literature surveys.

There have been various attempts to compete with Google Scholar, but few have lasted very long or provided value. The Allen Institute for Artificial Intelligence has launched its own Google Scholar called Semantic Scholar. For the time being, they have only indexed computer science papers, and their coverage falls short of what Google Scholar can offer. Still, competition is always welcome!

I am very excited about one of the features they have added: the automatic identification of influential citations. That is something I have long wanted to see… and it is finally here! In time, this might come to play a very important role.

Let me explain.

Scientists play this game where they try to publish as many papers as possible, and to get as many people as possible to cite their papers. If you are any good, you will produce some papers, and a few people will read and cite your work.

So we have started counting references as a way to measure a scientist’s worth. And we also measure how important a given research paper is based on how often it has been cited.

That sounds reasonable… until you look at the problem more closely. Once you look at how and why people cite previous work, you realize that most citations are “shallow”. You might build your new paper on one or two influential papers, maybe 3 or 4… but you rarely build on 20, 30 or 50 previous research papers. In fact, you probably haven’t read half of the papers you are citing.

If we are going to use citation counting as a proxy for quality, we need a way to tell apart the meaningful references from the shallow ones. Surely machine learning can help!

Back in 2012, I asked why it wasn’t done. Encouraged by the reactions I got, we collected data from many helpful volunteers. The dataset with the list of volunteers who helped is still available.

The next year (2013), we wrote a paper about it: Measuring academic influence: Not all citations are equal (published by JASIST in 2015). The work shows that, yes, indeed, machine learning can identify influential references. There is no good reason to consider all citations as having equal weights. We also discussed many of the potential applications such as better rankings for researchers, better paper recommender systems and so forth. And then among others, Valenzuela et al. wrote a follow-up paper, using a lot more data: Identifying Meaningful Citations.

What gets me really excited is that the idea has now been put in practice: as of this week, Semantic Scholar allows you to browse the references of a paper ranked by how influential the reference was to this particular work. Just search for a paper and look for the references said to have “strongly influenced this paper”.

I hope that people will quickly build on the idea. Instead of stupidly counting how often someone has been cited, you should be tracking the work that he has influenced. If you have liked a paper, why not recommend paper that it has strongly influenced?

This is of course only the beginning. If you stop looking at research papers as silly bags of words having some shallow metadata… and instead throw the full might of machine learning at it… who knows what is possible!

Whenever people lament that technology is stalling, I just think that they are not very observant. Technology keeps on granting my wishes, one after the other!

Credit: I am grateful to Peter Turney for pointing out this feature to me.

Many famous people have recently grown concerned that artificial intelligence is going to become a threat to humanity in the near future. The wealthy entrepreneur Elon Musk and the famous physicist Stephen Hawking are among them.

It is obvious that any technology, including artificial intelligence, can be used to cause harm. Information technology can be turned into a weapon.

But I do not think that it is what Hawking and Musk fear. Here is what Hawking said:

It [artificial intelligence] would take off on its own, and re-design itself at an ever increasing rate, Humans, who are limited by slow biological evolution, couldn’t compete, and would be superseded.

Here is what Musk said:

With artificial intelligence we are summoning the demon. In all those stories where there’s the guy with the pentagram and the holy water, it’s like – yeah, he’s sure he can control the demon. Doesn’t work out,(…)

So far from being merely worried about potential misuse of technology, Hawking and Musk consider a scenario more like this:

• Machines increasingly acquire sophisticated cognitive skills. They learned to play Chess better than human beings. Soon, they will pass as human beings online. It is only a matter of time before someone can produce software that passes the American Scholastic Aptitude Test with scores higher than the average human being… and soon after, better than any human being.
• Then, at some point, machines will wake up, become conscious, reach “general intelligence” and we are facing a new species that might decide to do away with us.

The first part of this scenario is coming true. We have cars, trains and airplanes without human pilots today… in 30 years, no insurer will be willing to cover you if you decide to drive your own car. It is all going to be automated. Factories are similarly going to be automated. Goods delivery will be automated. Medical diagnostic will be automated. In 30 years, we will have computing devices that are far more powerful than the naked brain. It is likely that they will use up a lot more energy and a lot more space than a human brain… but a computing device can have instant access to all of the Internet in ways that no human brain can.

What we often fail to realize is that “artificial intelligence” is not something that will happen suddenly. It is a process, and we are far along in this process. A vending machine is very much an automated store. An automated teller, as you can find anywhere in the world, is as the term implies… a teller that has been replaced by “artificial intelligence”.

There is a myth that machines will suddenly become qualitatively smarter. They will acquire a soul or something like it.

First, there is the notion that machines will acquire consciousness in a sudden fashion. So my laptop is not conscious, but maybe the next iteration or the one after that, with the right software will “acquire” consciousness. The problem with consciousness is that it is a purely intuitive notion that appears to have no counterpart in the objective world. We “think” we are conscious because we think “I am going to open this door” and then we open the door. So the “voice” in our head is what is in charge. But that is an illusion as demonstrated by Benjamin Libert. What is clearly established is that you can describe and announce your decisions only after the fact. By the time you are ready to announce that you will open the door, your brain has already taken its decision. We think that we are conscious our of surroundings in pure real time, but that is again an illusion: our brain spends a great deal of efforts processing our senses and constructing a model. That is why there are perceptible delays in when responding to stimuli. Your brain gets some input, updates a model and reacts accordingly, just like any computer would do. So it is not clear that my laptop is any less conscious than I am though it is clear that it can react much faster than I can. Free will is also an illusion. There is simply no test, no objective measurement that you can use to establish how conscious or free is a computing device or brain.

Second, there is the notion of general intelligence. The belief is that computers are specialized devices that can do only what they have been programmed for, whereas biological beings can adapt to any new task. It is true that mammals can change their behavior when faced with new conditions. But you must first consider that this ability is quite variable in living beings. If the climate gets colder, frogs do not just decide to put on coats. Frogs do what frogs do in a very predictable manner. But even human beings have also limited abilities to adapt. The obesity epidemic is an obvious example: for thousands of years, human beings starved to death… all of a sudden, food is abundant… what do we do? We eat too much and shorten our lives in the process. We did away with most predators and live in wonderfully safe cities… Yet if you are threatened of being fired, even if you know that you are physically safe and will never go hungry… your body react as if you were being attacked by a predator, and makes you more prone to act on instinct… exactly the opposite of good sense… So the evidence is clear: we are slaves to our programming. It is true that human beings can learn to do String Theory. We can acquire new skills that were not programmed into us, to some extent. That sets us apart from frogs, as frogs are unlikely to acquire a new way to swim or to eat. But it does not set us apart from software. In fact, software is much easier to expand than the human mind. Again, this notion of general intelligence seems to be an ill-defined intuitive idea that comforts us but has little to do with objective reality.

Are computers going to become smarter than people? They already are in many ways that matter. They can plan trips across complex road networks better than we can. Computers will continue to catch up and surpass the human brain. We can make an educated guess as to how far this process will be in 30 years: very far. Nobody can know what effect this will have on humanity. But we can probably stop worrying about machines acquiring consciousness or “general” intelligence all of a sudden and turning against us as a consequence. Stop watching so many bad scifi movies!

We all know the regular multiplication that we learn in school. To multiply a number by 3, you can multiply a number by two and add it with itself. Programmers write:

a * 3 = a + (a<<1)

where a<<1 means "shift the bit values by one to the left, filling in with a zero". That's a multiplication by two. So a multiplication can be described as a succession of shifts and additions.

But there is another type of multiplication that you are only ever going to learn if you study advanced algebra or cryptography: carry-less multiplication (also called "polynomial multiplication). When multiplying by powers of two, it works the same as regular multiplication. However, when you multiply numbers that are not powers of two, you combine the results with a bitwise exclusive OR (XOR). Programmers like to write "XOR" as "^", so multiplying by 3 in carry-less mode becomes:

a "*" 3 = a ^ (a<<1)

where I put the multiplication symbol (*) used by programmers in quotes ("*") to indicate that I use the carry-less multiplication.

Why should you care about carry-less multiplications? It is actually handier than you might expect.

When you multiply two numbers by 3, you would assume that

a * 3 == b * 3

is only true if a has the same value as b. And this works because in an actual computer using 64-bit or 32-bit arithmetic because 3 is coprime with any power of two (meaning that their greatest common factor is 1).

The cool thing about this is that there is an inverse for each odd integer. For example, we have that

0xAAAAAAAB * 3 == 1.

Sadly, troubles start if you multiply two numbers by an even number. In a computer, it is entirely possible to have

a * 4 == b * 4

without a being equal to b. And, of course, the number 4 has no inverse.

Recall that a good hash function is a function where different inputs are unlikely to produce the same value. So multiplying by an even number is troublesome.

We can "fix" this up by using the regular arithmetic modulo a prime number. For example, Euler found out that 2³¹ -1 (or 0x7FFFFFFF) is a prime number. This is called a Mersenne prime because its value is just one off from being a power of two. We can then define a new multiplication modulo a prime:

a '*' b = (a * b) % 0x7FFFFFFF.

With this modular arithmetic, everything is almost fine again. If you have

a '*' 4 == b '*' 4

then you know that a must be equal to b.

So problem solved, right? Well... You carry this messy prime number everywhere. It makes everything more complicated. For example, you cannot work with all 32-bit numbers. Both 0x7FFFFFFF and 0 are zero. We have 0x80000000 == 1 and so forth.

What if there were prime numbers that are powers of two? There is no such thing... when using regular arithmetic... But there are "prime numbers" (called "irreducible polynomials" by mathematicians) that act a bit like they are powers of two when using carry-less multiplications.

With carry-less multiplications, it is possible to define a modulo operation such that

modulo(a "*" c) == modulo(b "*" c)

implies a == b. And it works with all 32-bit or 64-bit integers.

That's very nice, isn't it?

Up until recently, however, this was mostly useful for cryptographers because computing the carry-less multiplications was slow and difficult.

However, something happened in the last few years. All major CPU vendors have introduced fast carry-less multiplications in their hardware (Intel, AMD, ARM, POWER). What is more, the latest Intel processors (Haswell and better) have a carry-less multiplication that is basically as fast as a regular multiplication, except maybe for a higher latency.

Cryptographers are happy: their fancy 128-bit hash functions are now much faster. But could this idea have applications outside cryptography?

To test the idea out, we created a non-cryptographic 64-bit hash function (CLHash). For good measure, we made it XOR universal: a strong property that ensures your algorithms will behave probabilistically speaking. Most of our functions is a series of carry-less multiplications and bitwise XOR.

It is fast. How fast is it? Let us look at the next table...

CPU cycles per input byte:

That's right: CLHash is much faster that competing alternatives as soon as your strings are a bit large. It can hash 8 input bytes per CPU cycles. You are more likely to run out of memory bandwidth than to wait for this hash function to complete. As far as we can tell, it might be the fastest 64-bit universal hash family on recent Intel processors, by quite a margin.

As usual, the software is available under a liberal open source license.

Further reading:

• Faster 64-bit universal hashing using carry-less multiplications, Journal of Cryptographic Engineering, 2015.

Modern software spends much time hashing objects. There are many fancy hash functions that are super fast. However, without getting fancy, we can easily double the speed of commonly used hash functions.

Java conveniently provides fast hash functions in its Arrays class. The Java engineers like to use a simple polynomial hash function:

for (int i = 0; i < len; i++) {
   h = 31 * h + val[i];
 }

That function is very fast. Unfortunately, as it is written, it is not optimally fast for long arrays. The problem comes from the multiplication. To hash n elements, we need to execute n multiplications, and each multiplication relies on the result from the previous iteration. This introduces a data dependency. If your processor takes 3 cycles to complete the multiplication, then it might be idle half the time. To compensate for the problem, you might unloop the function as follows:

for (; i + 3 < len; i += 4) {
   h = 31 * 31 * 31 * 31 * h 
       + 31 * 31 * 31 * val[i] 
       + 31 * 31 * val[i + 1] 
       + 31 * val[i + 2] 
       + val[i + 3];
}
for (; i < len; i++) {
   h = 31 * h + val[i];
}

This new function breaks the data dependency. The four multiplications from the first loop can be done together. In the worst case, your processor can issue the multiplications one after the other, but without waiting for the previous one to complete. What is even better is that it can enter the next loop even before all the multiplications have time to finish, and begin new multiplications that do not depend on the variable h. For better effect, you can extend this process to blocks of 8 values, instead of blocks of 4 values.

So how much faster is the result? To hash a 64-byte char array on my machine…

• the standard Java function takes 54 nanoseconds,
• the version processing blocks of 4 values takes 36 nanoseconds,
• and the version processing blocks of 8 values takes 32 nanoseconds.

So a little bit of easy unrolling almost doubles the execution speed for moderately long strings compared to the standard Java implementation.

You can check my source code.

Further reading:

• Faster 64-bit universal hashing using carry-less multiplications, Journal of Cryptographic Engineering, 2015.
• Strongly universal string hashing is fast, Computer Journal 57(11), 2014.

See also Duff’s device for an entertaining and slightly related hack.

Though we have plenty of memory in our computers, there are still cases where you want to minimize memory usage if only to avoid expensive cache faults.

To compare the memory usage of various standard map data structures, I wrote a small program where I create a map from the value k to the value k where k ranges from 1 to a 100,000, using either a string or integer representation of the value k. As a special case, I also create an array that contains two strings, or two integers, for each value of k. This is “optimal” as far as memory usage is concerned since only the keys and values are stored (plus some small overhead for the one array). Since my test is in Java, I store integers using the Integer class, and strings using the String class.

The worst case is given by the LinkedHashMap which uses twice as much space as an array in the Integer, Integer scenario.

I have also added the fastutil library to the tests. Its hash maps use open addressing, which has reduced memory usage (at the expense of expecting good hash functions). The savings are modest in this test (10%). However, in the Integer-Integer test, I used the library’s ability to work with native ints, instead of Integer objects. The savings are much more significant in that instance: for each pair of 32-bit integers, we use only 21 bytes, compared to 74.5 bytes for the HashMap class.

Looking at these number, we must conclude that the relative overhead due to the map data structure is small. Of course, Java objects eat up a lot of memory. Each Integer object appears to take 16 bytes. Each String object appears to use at least 40 bytes. That’s for the objects themselves. To use them inside another data structure, you have to pay the price of a pointer to the object.

In Java, the best way to save memory is to use a library, like fastutil, that works directly with native types.

Conclusion: Whether you use a TreeMap or HashMap seems to have very little effect on your memory usage.

Note: Please do not trust my numbers, review my code instead.

After arrays and linked lists, one of the first data structures computer-science students learn is the search tree. It usually starts with the binary search tree, and then students move on to B-trees for greater scalability.

Search trees are a common mechanism used to implement key-value maps (like a dictionary). Almost all databases have some form of B-tree underneath. In C++, up until recently, default map objects were search trees. In Java, you have the TreeMap class.

In contrast to the search tree, we have the hash map or hash table. Hash maps have faster single look-ups, but because the keys are not ordered physically, traversing the keys in sorted order can be much slower. And it might require fully sorting the keys as part of the iteration process, if you want to go through the keys in order.

In any case, if technical interviews and computer-science classes make a big deal of search trees, you’d think they were ubiquitous. And yet, they are not. Hash maps are what is ubiquitous.

• JavaScript, maybe the most widely used language in the world, does not have search trees part of the language. The language provides an Object type that can be used as a key-value store, but the keys are not sorted in natural order. Because it is somewhat bug prone to rely on the Object type to provide a map functionality, the language recently acquired a Map type, but it is again a wrapper around what must be a hash map. Maps are “sorted” in insertion order, probably through a linked list so that, at least, the key order is not random.
• Python, another popular language, is like JavaScript. It provides an all-purpose dict type that is effectively a map, but if you were to store the keys ‘a’, ‘b’, ‘c’, it might give them back to you as ‘a’, ‘c’, ‘b’. (Try {'a': 0, 'b': 0, 'c': 0} for example.) That is, a dict is a hash map. Python has an OrderedDict class, but it merely remembers the order in which the keys were added (like JavaScript’s Map). So there is no search tree to be found!
• The Go language (golang) provides a map class, but we can be sure there is no underlying search tree, since Go randomizes the key order by design! (To prevent users from relying on key order.)

What does it mean? It means that millions of programmers program all day long without ever using a search tree, except maybe when they access their database.

Though key-value stores are essential to programmers, the functions offered by a search tree are much less important to them. This suggests that programmers access their data mostly in random order, or in order of insertion, not in natural order.

Further reading: Scott Meyers has an article showing that hash maps essentially outperform all other look-ups except for tiny ones where a sequential search is best.

Update: It is commonly stated that a hash map uses more memory. That might not be generally true however. In a test of hash maps against tree maps in Java, I found both to have comparable memory usage.