Archive for February, 2008

Multi-threading Memory

As I’ve written before, multi-threaded code is hard to write. It becomes even harder to write when you find that lock contention is an efficiency issue. On a modern multi-core system locks require some sort of memory cache coordination between the various cores. If your program is written using fine-grained locks which may be held by threads running on different cores, access to those locks can become relatively expensive. For high performance code it then becomes desirable to avoid the locks when possible.

When you do this, you have to understand memory barriers. A memory barrier enforces a weak global ordering on memory reads and writes. Without a memory barrier, depending on cache behaviour, it is quite possible for one core to write A before B but for another core to see the write to B before it sees the write to A. Memory barriers enforce consistency.

Unfortunately, different architecture define memory barriers in different ways. And different implementations of different architecture implement them in different ways. So it is very easy to write code which works reliably in some places but fails occasionally in others.

Also, the compiler knows nothing about memory barriers (this will change to some extent with the next C++ standard and the atomic<> types). The compiler is generally free to casually reorder memory reads and writes as long as the final result is correct. When writing lock-free code using memory barriers, you need to carefully indicate what you are doing in two different ways: once for the processor and once for the compiler. This will normally be done via some sort of inline assembler construct. And of course you want to make this run as efficiently as possible, since that is the point of the exercise in the first place.

So basically getting all this right is a big hairball. The next C++ standard will push this hairball onto the compiler and library implementors. The types aren’t all that easy to understand, but at least they should work correctly. Until then, or when working in C, it’s really hard to write correct portable lock-free code. Better to avoid fine-grained locks, I think, or at least to avoid contention for them.

Some people argue that transactional memory will solve these problems. I am very skeptical of this. I’ll write more about this later.

Comments (5)

Eat Food

I recently read “In Defense of Food” by Michael Pollan. It’s not as weirdly fascinating as his earlier book “The Omnivore’s Dilemma,” but it has a lot of interesting information.

What I found most interesting was the shift in the recommendations of the McGovern commision on nutrition in 1977. This was the first attempt to recommend a national diet for the U.S.; previous commissions had just set the desired limits of certain vitamins. The 1977 commission was originally going to say something along the lines of “eat less fatty food, such as meat and dairy products.”

This statement expressed the majority opinion of nutritional scientists at the time, although it had relatively little support from scientific studies. It’s very hard to do a scientific study of a dietary shift, as is pretty clear if you think about it. You can’t have a proper control group, as people are obviously aware of what they are eating. You have to trust people to correctly report what they eat, which they will not do. So you can do a reasonably study of dietary supplements, but you can’t do a reasonable study of a significant change to overall diet. An inevitable effect is that nutrition recommendations tend to focus on supplements, which may or may not actually be the healthiest choice. So whether it is indeed healthier to eat less fatty food remains an open question, which may never be finally resolved; some recent studies suggest that it makes no difference.

Anyhow, the McGovern commission ran into immediate political trouble. The meat and dairy lobbies were certainly not happy about a recommendation to eat less of the food they produced. There is no lobby for people to be healthier–no specific industry benefits from healthy people. So the recommendation was changed to “eat more low-fat foods.” Note the significant shift from “eat less” to “eat more.”

Also in the 1970s the U.S. Farm Bill introduced a major shift, from paying farmers to let their fields lie fallow to paying them to actually grow food. That certainly makes sense on the surface. But the result was a massive increase in the amount of food being produced in the U.S., mostly in the form of corn. The price of corn dropped, and there was a lot of corn on the market looking for buyers.

So we had a lot more food being produced, and we had a government suggestion that people should eat more low-fat food. Fortunately all that corn could be turned into corn syrup, which while being a high-calorie food is low in fat. Many new product were created, labelled as being low-fat and therefore healthy. The general trend was that people started eating these new low-fat, healthy foods in addition to the meat and dairy they were already eating.

Eventual result: the massive increase in obesity and type II diabetes that we see today. This is not to excuse people for over-eating; for most of us, eating food is a choice. But people were given bad information, and they were given cheap unhealthy food, and the result is not unexpected.

Pollan’s overall recommendation for diet is “eat food, not too much, mostly plants.” It’s an interesting recommendation mainly because it sounds reasonably simple, yet many people do not follow it. By “eat food” he means that one should eat traditional, well-recognized types of food, and to avoid synthetic food products. Eat pasta, bread, milk, fruit, vegetables; don’t eat artificial foods with long lists of ingredients some of which you have never heard of. Avoid food products which make extensive health claims.

All very sensible advice, yet somehow difficult to follow in our culture.

Comments (3)

Debugging

I think that people who take a computer science degree in college should be required to study debugging. For better or for worse, debugging is an essential part of programming. However, most programmers are left to learn it on their own, in a way that is not true of many other aspects of programming. I believe that it is possible for a programmer to learn to become a better debugger. It follows that it should be possible to teach it.

Naturally it is more important to write good code than it is to debug code. However, reality is that most of us will work with code which was written by other people. Even the best coder will still have to fix bugs in other people’s code. So debugging is an essential skill in practice.

A few years ago I wrote an essay on debugging. I think it still holds up pretty well, though it is really just an introduction.

Comments

Jumper Again

I did go to the movie version of Jumper. It had nothing to do with the book. I think there were about three or four scenes from the book in the movie, all at the very beginning. The characters were all completely different, although they had the same names.

In general the movie was pretty bad. The story was full of logic holes. The characters were completely unbelievable. The dialogue was badly written. The acting was stilted–not even Samuel L. Jackson could make his character remotely believable. On the plus side, the special effects were generally pretty good.

Also on the plus side, the story was so completely unlike the book that it doesn’t spoil the book.

Don’t go to this movie, even if it is still in the theaters. Save your money.

Comments

Winter

Visiting Maine at this time of year reminds me how winter is the limiting factor for life in the north. Every plant and animal which lives there has a complex and energy intensive survival mechanism for the cold: insulation, hibernation, migration, etc. Where I live now in California the limiting factor is the long, dry, summer. The adaptations here are less dramatic, but just as important.

Probably the places with the fewest environmental limits are the rain forests. There, the limit instead becomes all the other living things. This leads to an interesting pattern: the northern plants and animals have wide ranges–roughly all around the world in the northern latitudes. Once they’ve learned how to survive the winter, they face no major other competition. In the rain forest, many plants and animals have vanishingly small ranges. Some insects only live on certain trees. Sometimes there will be only one of those trees in a square mile. Where the limit is other life, evolution leads to hyper-specialization seeking any advantage. Where the limit is the environment, evolution leads to generality once the environment is survivable.

This is of course why the rain forest is so remarkably abundant yet so strangely fragile. The northern evergreens will still be here long after we’ve reduced the rainforest to national parks and zoos.

Comments

« Previous entries Next Page » Next Page »