Science and Technology links (January 19th, 2019)

  1. Losing even just a bit of weight can be enough to restore fertility in women.
  2. Digital technology does not appear to have a significant negative effect on teenagers, according to an article published by Nature.
  3. According to an article published by Nature, woody vegetation cover over sub-Saharan Africa increased by 8% over the past three decades. This is part of a larger trend: the Earth is getting greener.
  4. The number of children in India has peaked. This suggests that the population of India will peak soon as well.
  5. Scientists are looking for chemical factors that either decrease or increase with age: normalizing these factors could slow or reverse aging. Nature reports on a factor called MANF which decreases with age in mice, human beings and flies. It seems than MANF supplements could have anti-aging benefits.
  6. Netflix is approaching 150 million subscribers. This means that about 2% of the world’s population is made of Netflix subscribers. This almost certainly underestimates the true reach of Netflix.
  7. In an article in the reputed Guardian newspaper from 2004, we can read:

    A secret report, suppressed by US defence chiefs and obtained by The Observer, warns that major European cities will be sunk beneath rising seas as Britain is plunged into a ‘Siberian’ climate by 2020. Nuclear conflict, mega-droughts, famine and widespread rioting will erupt across the world. (…) Already (…) the planet is carrying a higher population than it can sustain. By 2020 ‘catastrophic’ shortages of water and energy supply will become increasingly harder to overcome, plunging the planet into war.

  8. Our brains are made of white and grey matter. Obesity correlates with lower gray matter volume in the brain.
  9. Men and women have (statistically) different cognitive abilities, with women being better at verbal tasks whereas men are better at spatial tasks. This survey concludes that homosexuals have abilities closer to the other sex:

    The meta-analysis revealed that homosexual men performed like heterosexual women in both male-favouring (e.g., spatial cognition) and female-favouring (e.g., verbal fluency) cognitive tests, while homosexual women performed like heterosexual men only in male-favouring tests. The magnitude of the sexual orientation difference varied across cognitive domains (larger for spatial abilities).

Faster intersections between sorted arrays with shotgun

A common problem within databases and search engines is to compute the intersection between two sorted array. Typically one array is much smaller than the other one.

The conventional strategy is the “galloping intersection”. In effect, you go through the values in the small arrays and then do a binary search in the large array. A binary search is a simple but effective algorithm to search through a sorted array. Given a target, you compare with with the midpoint value. If your target is smaller than the midpoint value, you search in the first half of the array, otherwise you search in the second half. You can recurse through the array in this manner, cutting the search space in half each time. Thus the search time is logarithmic.

If the small array has M elements and the large array has N elements, then the complexity of a galloping search is O(M log N). In fact, you can be more precise: you never need more than M * log N + M comparisons.

Can you do better? You might.

Let me describe an improved strategy which I call “shotgun intersection”. It has been in production use for quite some time, through the CRoaring library, a C/C++ implementation of Roaring Bitmaps.

The idea is that galloping search implies multiple binary searches in sequence through basically the same array. Doing them consecutively might not be best. A binary search, when the large array is not in cache, is memory-bound: it waits for the memory subsystem to deliver the data. So you are constantly waiting. What if you tried to do something else while you wait. What about starting right away on the next binary search?

That is how a shotgun search works. You take, say, the first four values from the small array. You load the midpoint value from the large array, then you compare all of your four values against this midpoint value. If the target value is larger, you set a corresponding index so that the next search will hit the second half of the array. And so forth. In effect, shotgun search does many binary searches at once.

I make my Java code available, if you want a full implementation.

Does it help? It does. Sometimes it helps a lot. Let us intersect an array made of 32 integers with an array made of 100 million sorted integers. I use a cannonlake processor with Java 8.

1-way 1.3 microseconds
4-way 0.9 microseconds

Credit: Shotgun intersections are based on an idea and an initial implementation by Nathan Kurz. I’d like to thank Travis Downs for inspiring discussions.

Science and Technology links (January 12th, 2019)

  1. You can buy a 512GB memory card for $140 from Amazon.
  2. We have been told for decades to avoid saturated fats, the kind found in meat, cheese and butter. After an extensive review, Grasgruber et al. conclude:

    Our results do not support the association between cardiovascular diseases and saturated fat, which is still contained in official dietary guidelines. In the absence of any scientific evidence connecting saturated fat with cardiovascular diseases, these findings show that current dietary recommendations regarding cardiovascular diseases should be seriously reconsidered.

  3. Stoet and Geary propose a new measure of gender inequality and conclude…

    We found that low levels of human development are typically associated with disadvantages for girls and women, while medium and high levels of development are typically associated with disadvantages for boys and men. Countries with the highest levels of human development are closest to gender parity, albeit typically with a slight advantage for women.

  4. Budish argues that Bitcoin would be hacked if it became sufficiently important economically.
  5. We can use deep-learning software to reconstruct intelligible speech from the human auditory cortex.
  6. Nelson’s research indicates that there will be more calories available per capita in 2050 than today, in all income quintiles, and even in an extreme climate change scenario. However, both obesity and dietery shortages (e.g., vitamin A) will remain a challenge:

    We must shift our emphasis from food security to nutrition security.

Science and Technology links (January 5th, 2019)

  1. There are nearly 70,000 centenarians in Japan.
  2. China’s population fell by 1.27 million in 2018.
  3. Obesity is associated with increased senescent cell burden and neuropsychiatric disorders, including anxiety and depression. Clearing senescent cells could alleviate these symptons.
  4. Women who come from families where the mother is the breadwinner are less likely to pursue a science degree at university level.
  5. Stronger men live longer:

    Muscular strength is inversely and independently associated with death from all causes and cancer in men, even after adjusting for cardiorespiratory fitness and other potential confounders.

  6. Inflammation is a crude but effective part of our immune system that serves as a first line of defense. It is necessary but tends to get out of hand as we age. Arai et al. found that your level of inflammation was a potential predictor of how likely you were to reach extreme old age:

    Inflammation is the prime candidate amongst potential determinants of mortality, capability and cognition up to extreme old age

  7. An article published by Nature argues for rejuvenation strategies:

    Ageing is associated with the functional decline of all tissues and a striking increase in many diseases. Although ageing has long been considered a one-way street, strategies to delay and potentially even reverse the ageing process have recently been developed. Here, we review four emerging rejuvenation strategies—systemic factors, metabolic manipulations, senescent cell ablation and cellular reprogramming—and discuss their mechanisms of action, cellular targets, potential trade-offs and application to human ageing.

  8. Childhood leukaemia is a feature of developed societies and has to do with the fact that children are insufficiently exposed to bacteria and infections.
  9. China has landed a rover on the far side of the Moon.
  10. While climate change models predict that as the world warms, biomass will decompose more quickly, which would send a lot more carbon dioxide into the atmosphere, new research finds that it may work the other way around: warmer temperature may reduce decomposition and carbon emissions.
  11. You can defeat Google’s captchas (meant to prove you are a human being) by taking the audio test and feeding it back to Google’s services to get a transcription.

Memory-level parallelism: Intel Skylake versus Intel Cannonlake

All programmers know about multicore parallelism: your CPU is made of several nearly independent processors (called cores) that can run instructions in parallel. However, our processors are parallel in many different ways. I am interested in a particular form of parallelism called “memory-level parallelism” where the same processor can issue several memory requests. This is an important form of parallelism because current memory subsystems have high latency: it can take dozens of nanoseconds or more between the moment the processor asks for data and the time the data comes back from RAM. The general trend has not been a positive one in this respect: in many cases, the more advanced and expensive the processor, the higher the latency. To compensate for the high latency, we have parallelism: you can ask for many data elements from the memory subsystems at the same time.

In earlier work, we showed that current Intel processors (Skylake microarchitecture) are limited to about ten concurrent memory requests whereas Apple’s A12 processor scale to 40 or more memory requests.

Intel just released a more recent microarchitecture (cannonlake) and we have been putting it to the test. Is Intel improving?

It seems so. In a benchmark where you randomly access a large array, using a number of separate paths (which I call “lanes”), we find that the cannonlake processor appears to support twice as many concurrent memory requests as the skylake processors.

The Skylake processor has lower latency (70 ns/query) compared to the Cannonlake processor (110 ns/query). Nevertheless, the Cannonlake is eventually able to beat the Skylake processor in bandwidth by a wide margin (12 GB/s vs 9 GB/s).

The story is similar to the Apple A12 experiments.

This suggests that even though future processors may not have lower latency when accessing memory, we might be better able to hide this latency through more parallelism.

Even if you are writing single-threaded code, you ought to think more and more about parallelism.

Our code is available.

Credit: Though all the mistakes are mine, this is joint work with Travis Downs.

Further details: Processors access the memory through pages. By default, many Intel systems have “small” pages (4kB). When doing random accesses in large memory regions, you are likely to access too many pages, so that you incur expensive “page misses” that lead to “page walks”. It is possible to use large page sizes, even “huge pages”. But since memory is allocated in pages and you may end up with many under-utilized pages if they are too large. In practice, under-utilized pages (sometimes called “memory fragmentation) can be detrimental to performance. To get the good results above, I use huge pages. Because there is just one large memory allocation in my tests, memory fragmentation is not a concern. With small pages, the Cannonlake processor loses its edge over Skylake: they are both limited to about 9 concurrent requests. Thankfully, on Linux, programmers can request huge pages with a madvise call when they know it is a good idea.

Important science and technology findings in 2018

  1. The Gompertz-Makeham law predicts statistically the mortality rate of human beings. The key takeaway is that it is an exponential function. Every few years, the mortality rate of a human being doubles. It is not unique to human beings: most mammals and many other animals have an exponentially rising mortality rate over time. It does not affect all animals, however. Lobsters do not appear to age like we do. Many trees age in reverse, meaning that their mortality rate diminishes over time. In 2018, a scientist studying naked mole rates for decades published an analysis of over 3,000 rats and found that their mortality rate remains constant throughout their life. We do not know why naked mole rates age differently from most other mammals.
  2. Type 1 diabetes is when your pancreas is unable to supply insulin to your cells. Though it can be treated with expensive and inconvenient insulin shots, there is no cure. In 2018, we found that a heart-disease drug can partially reverse type 1 diabetes. This could make some diabetics less dependent on insulin.
  3. Though artificial intelligence has been making a lot of progress in tasks such as image classification and game playing, we are still a long way from being able to intelligently animate human-like body parts like hands. Simple tasks like folding laundry or turning a door knob are still a massive challenge. In 2018, researchers from OpenAI have trained a human-like robot hand to manipulate objects like we would.
  4. Older people tend to have a less efficient immune system. In 2018, we learned that we can at least partially reverse age-related immune-system decline using drugs. It substantially reduces infections in older people.
  5. The human genome project set forth in 1990 to map the human chromosomes. We thought at the time that human beings would have 100,000 genes, but they have only about 25,000 genes. The map was completed in 2003. Yet applications of the human genome project have been scarce. In 2018, the first gene-silencing drug was approved in the USA.
  6. Electrocardiograms (ECG) have been used since the 19th century to monitor human hearts. The first commercially available ECG machines were produced at the beginning of the 20th century but they remain specialized devices mostly just used within hospitals. They are also somewhat invasive. In 2018, Apple released a watch with government-approved ECG (heart monitoring) capabilities.
  7. CRISPR/Cas9 is technique developed in 2012 to edit the genes of living organisms. It is unclear whether it is safe to use it on human beings… Using this technique, a Chinese researcher helped produce the first genetically modified babies, they may be immune to HIV.

Science and Technology links (December 29th, 2018)

  1. Low-dose radiation from A-bombs elongated lifespan and reduced cancer mortality relative to un-irradiated individuals (Sutou, 2018):

    The US National Academy of Sciences (NAS) presented the linear no-threshold hypothesis (LNT) in 1956, which indicates that the lowest doses of ionizing radiation are hazardous in proportion to the dose. This spurious hypothesis was not based on solid data. (…) A-bomb survivors (…) showed longer than average lifespans. Average solid cancer death ratios of(…) A-bomb survivors (…) were lower than the average for Japanese people (…), essentially invalidating the LNT model. Nevertheless, LNT has served as the basis of radiation regulation policy. If it were not for LNT, tremendous human, social, and economic losses would not have occurred in the aftermath of the Fukushima Daiichi nuclear plant accident. For many reasons, LNT must be revised or abolished, with changes based not on policy but on science.

    This is important work. I am surprised at how few people know about hormesis. Many people assume that if you avoid stress, toxins and challenges, you will maximize your health and longevity. That is just flat out wrong.

  2. In climate talks, we use year 1850 as a reference: the implicit goal is to maintain Earth’s global temperature close to the global temperature that existed in year 1850 (say within 1.5 degrees). To my knowledge, nothing makes year 1850 special. In fact, in the absence of both ancient and recent carbon emissions from agriculture and industrialization, current global average temperatures would likely have been about 1.3 degrees lower than they were around 1850 (Vavrus et al., Nature 2018). We were headed down toward another glaciation and, instead, due to human beings, we are headed toward warmer and warmer temperatures. Left unchecked, neither direction is desirable. As argued by Deutsch in the Beginning of Infinity, we have no choice but to accept that there is no such thing as “sustainability” (which assumes an ideal steady state) and that we must learn to engineer our climate.
  3. Human beings do not originate from a single region in Africa: the story of our origin is complicated, involving a mix of different populations and cultures.
  4. McGuff and Litte (2009) write:

    there is no additional physiological advantage afforded to one’s body, including endurance or cardio benefits, by training that lasts more than six to nine minutes a week.

  5. The videogame Fortnite lead to 3 billion dollars in profit for its creators. It has 200 million players.
  6. In older mammals, the skin loses fat. Zhang et al. restored the ability of skin in older mice to store fat, thus making the skin more resistant to some infections.
  7. Students who make friends and study with them tend to do better. This is painfully obvious to anyone who has given serious thought to how schooling works.

Science and Technology links (December 22nd 2018)

  1. For equity reasons, many people advocate for double-blind peer review, meaning that the author does not know who the reviewer is, nor does the reviewer know who the author is. It is believed (despite little hard positive evidence and some contrary evidence) that this is surely benefificial to female authors and minorities. Cox and Montgomerie find that:

    These analyses suggest that double-blind review does not currently increase the incidence of female authorship in the journals studied here. We conclude, at least for these journals, that double-blind review does not benefit female authors and may, in the long run, be detrimental.

    Why do they say it may be detrimental?

    Firstly, making everything anonymous is hard work. And ressources are finite: we are already struggling to find time and people to review manuscripts… adding to the burden has a cost. Thus we must ensure that there are comparable benefits. You shouldn’t think for a minute that making science harder and more expensive is going to necessarily benefit women and minorities. Raising the costs usually works against inclusion.

    Secondly, they observe empirically that publications by women are less likely to appear in double-blind-review journals than in conventional journals. Why is that? If double-blind reviews are obviously beneficial to women, they would flock the double-blind journals… but they do not. Either women are misguided or else, more likely, double-blind reviews do not favor women.

    And, finally, there may be substantial benefits to the authors and the community in the reviewers knowing who they are. It is simply a fact that the identity of the authors is an important factor when assessing a piece of scientific work. Ultimately, we tend to reward sustained high quality work with more credibility. You want authors to have skin in the game: if their work is bad, then they should pay a price (more scrutiny of their work in the future) and when their work is consistently good, they should be rewarded (given more implicit trust).

  2. The price of lithium-ion batteries has fallen by 73% between 2010 and 2016. (Source: Bloomberg) However, it does not mean that these batteries are getting better at a similar rate: it seems that even though the price is falling, the physical quality of the batteries remains similar.
  3. Scientists have created viable human hair follicles from cultured human cells. (Source: Nature)
  4. There is interest in NAD supplements for anti-aging purposes. Xie et al. (2018) show cognitive benefits due to NAD supplements in old mice.
  5. Bernstein et al. (2018) point out that continuous and sustained social interactions reduce individual exploration. In other words, to be highly original, you do need to close your door and stop answering emails and phone calls for a time.

Fast Bounded Random Numbers on GPUs

We often use random numbers in software in applications such as simulations or machine learning. Fast random number generators tend to produce integers in [0,232) or [0,264). Yet many applications require integers in a given interval, say the interval {0,1,2,3,4,5,6,7}. Thus standard libraries frequently provide a way to request an integer within a range.

How does it work underneath? Typically, a 64-bit or 32-bit integer is produced, and then it is converted into an integer within the desired range. Unfortunately, as pointed out in details by Melissa O’Neill, doing so without introducing undue biases is slow. That is, it can take more time to convert the integer to the range than to produce the random integer in the first place!

In Fast Random Integer Generation in an Interval, we show how to drastically accelerate this computation compared to the standard libraries. The main trick is to avoid as much as possible the use of division instructions (since they are slower). Bernardt Duvenhage has a great talk on the application of this technique in Python. There is an illustrative benchmark on GitHub.

In the paper, there is a precautionary note about the applicability of this technique to GPUs. Indeed, there are substantial differences between general purposes 64-bit processors and common GPUs (32-bit). A reader, Norbert Juffa, reached out to me to point out that the note might be unwarranted. Juffa wrote a benchmark using the NVIDIA API (CUDA) to support his claim.

The fast function that avoids divisions as much as possible can be expressed using a few lines of C.

// returns value in [0,s)
uint64_t nearlydivisionless (uint64_t s)  {
    uint64_t x = random64 ();
   // compute ( x * s ) >> 64
    uint64_t h = __umul64hi (x, s); 
    uint64_t l = x * s;
    if (l < s) {
        uint64_t t = -s % s;
        while (l < t) {
            x = random64 ();
            h =__umul64hi (x, s);
            l = x * s;
        }
    }
    return h;
}

What Juffa does is to generate 10,000,000 integers in the interval [0,500,000] from Marsaglia’s KISS64 random number generator. On a Quadro P2000 Nvidia card, he shows that using an approach that minimizes the use of divisions is much faster.

OpenBSD-like 5 ms
Java-like 2.9 ms
Our approach 1.4 ms

I make Juffra’s code available.

Sorting strings properly is stupidly hard

Programming languages make it hard to sort arrays properly. Look at how JavaScript sorts arrays of integers:

> v = [1,3,2,10]
[ 1, 3, 2, 10 ]
> v.sort()
[ 1, 10, 2, 3 ]

You need a magical incantation to get the right result:

> v.sort((a,b)=>a-b)
[ 1, 2, 3, 10 ]

Though this bad default can create bugs, it is probably not the source of too many frustrations. However, sorting strings alphabetically is a real problem. Let us see how various languages do it.

JavaScript:

> var v = ["e", "a", "é","f"]
> v.sort()
[ 'a', 'e', 'f', 'é' ]
> v = ["a","b","A","B"]
> v.sort()
[ 'A', 'B', 'a', 'b' ]

Python:

>>> x=["e","a","é","f"]
>>> x.sort()
>>> x
['a', 'e', 'f', 'é']
>>> x=["a","A","b","B"]
>>> x.sort()
>>> x
['A', 'B', 'a', 'b']

Swift:

  1> var x = ["e","a","é","f"] 
  2> x.sorted()
$R0: [String] = 4 values {
  [0] = "a"
  [1] = "e"
  [2] = "f"
  [3] = "é"
  1>  var x = ["a","b","A","B"]
  2> x.sorted() 
$R1: [String] = 4 values {
  [0] = "A"
  [1] = "B"
  [2] = "a"
  [3] = "b"
}

As far as I can tell, by default, these languages apply crude code-point sorting. Human beings understand that the characters e, é, E, É, è, ê, and so forth, should be considered as the same letter (e) with accents. There are exceptions to this rule, but the default which consists in sorting accentuated characters after the letter ‘z’ is just not reasonable. The way case is handled is patently stupid. You might prefer A to come before a, or vice versa, but no human being would ever sort the letters as A,B,a,b or a,b,A,B.

There are standards for sorting strings, such as the Unicode Collation Algorithm.

To get a sensible default, programming languages force you to use complicated code. In JavaScript, it is burdensome but easy enough….

> v.sort(Intl.Collator().compare)
[ 'a', 'e', 'é', 'f' ]

However, I am not sure what the equivalent is in Python and Swift. It does not jump at me in the documentation of the respective standard librairies. I did not even look at it for other popular programming languages like Go, C++, and so forth.

It is unacceptably difficult to do the “right thing”. The net result is that many programmers do not sort strings properly. If you use a natural language with non-English characters, you see the effect in many applications. It looks bad.

Thankfully, most major software products get it right. Microsoft Office, Google Docs, Apple apps… all do the right thing. It creeps up in small budget applications. I have to use one in my daily life as an employee of a public university, and it annoys me.

We should do better.

Further reading:International Components for Unicode