Writing
The wheel is often mentioned as the cornerstone invention of our civilization. I’m not arguing it’s not true, but I consider writing as one of the most important inventions.
Information management such as precise collection and transfer is crucial for any civilization to make progress. Written information can be exchanged without errors. This includes everyday communication, trade, history, law. Writing also enabled progress in engineering and science.
Humans are not a good medium of information, because their memory is unreliable. They forget things, or misinterpret them. Religion and knowledge used to be passed from shaman to shaman using spoken language, whatever they forgot, had to be rediscovered again. But after the invention of writing humans started organizing into bigger groups and started creating new, magnificent technologies.
Advanced religion, which was also an important piece of the evolution of the civilization, was also not possible without writing. Every tribe used to have their own set of stories and of course they used to clash over whose stories are right. Once religious manuscripts were created, people started uniting over religion, what helped the development of nations.
Next time you’re writing something, realize that you’re using one of the most important inventions of our civilization.
Multithreading
Recently when reviewing some piece of code, which was going to be used in a multithreaded environment, I came to the conclusion that writing thread-safe code is twice as difficult as regular single-threaded code.
Concurrency adds another dimension to programs. A function in a multi-threaded program must be aware that other pieces of code will be executing at the same time. What happens when two threads call this function simultaneously? What happens if other functions start changing the data this function uses?
Not only code has to be written making sure that nobody messes it up during execution, but the lifetime of resources must also be considered. The resources used by a thread must be allocated and freed even more diligently than in single-threaded programs. Threads are also resources, while it’s easy to spawn them, stopping them must also be planned.
Here are a few tips for those new to the world of multiple threads of execution. There are exceptions to every “rule” described below, so always stay alert!
- Use mutexes to guard resources which can be modified simultaneously by multiple threads.
- Reading is a thread-safe operation, unless someone can modify the data you’re reading. Data which is initialized once before any threads are created or const data does not have to be guarded – unless multiple threads can attempt to initialize it.
- Use as few mutexes as possible to reduce the risk of deadlocks.
- When using multiple mutexes to lock multiple resources, always lock mutexes in the same order and unlock them in reverse order to avoid deadlocks.
- Prefer lock-free constructs. They usually rely on atomic operations. Creating a good lock-free construct can be quite tricky. If multiple atomic operations are needed, maybe it’s time to use a mutex – multiple atomic operations can lead to race conditions.
- A good design pattern applicable to many situations is a queue with worker threads. Such queue can be designed to be fed by either one or many threads, which will keep adding elements to its tail. Worker threads will keep retrieving items from the head of the queue. In some situations a lock-free queue is useful, in other situations it’s good to have a semaphore to indicate to worker threads if something is in the queue and a mutex to guard the queue’s guts. Such queue is quite easy to write and reasonably safe.
- Alternatively you can think of such queue as of a messaging mechanism, where threads can interchange information using messages. Software which relies on message passing instead of sharing data between threads statistically has a lower chance of defects.
- Another relatively safe construct are barriers. In a model with barriers you create multiple seemingly identical threads, which occasionally wait on a barrier to synchronize with each other. All threads in a group must stop on a barrier, only then can they continue further execution. The programming model based on barriers can be found in CUDA or OpenCL and is relatively safe, although deadlocks may occur if threads have a way to avoiding barriers.
- Group resources into classes and guard them with a single mutex. Have all the public functions of such classes lock the mutex.
- In general highly cohesive modules are easier to maintain in multi-threaded environments.
- For every function make sure that it is safe to call it simultaneously from multiple threads.
- For every class make sure that it is safe to call any number and combination of the class’ function simultaneously from multiple threads.
- Make all class’ member variables private. This is generally encouraged in C++, but it’s even more important for thread safety.
- Make sure that functions you call are thread-safe.
- Avoid global variables. You can get away with them in single-threaded programs, but they can and will mess things up severely in multi-threaded code.
- Avoid static variables. They are just a form of globals and will also lead to problems.
- Avoid nested mutexes. Some platforms allow nested mutex locking, such as Windows’ critical section or a recursive POSIX mutex. The problem is that when you determine that you need a recursive mutex it is a symptom of a bad multi-threaded design. There are exceptions to this, as always, but usually the code will sooner or later get out of hand and you will spend a lot of time debugging spurious failures. Once you need a recursive mutex it indicates that there is no one, clean way to enter a function or section of code and users of the code may enter into situations which you failed to predict.
- Avoid passing function arguments and local variables to other threads by pointer or reference. This way you can rely on them as always being thread-safe.
- When passing data between threads, design well when that data will be created and destroyed. Make sure it doesn’t leak. Make sure it isn’t accessed after it’s destroyed.
- When writing C or C++ code, avoid the volatile keyword, unless you use it for hardware resources and you know exactly what you are doing. The volatile keyword has nothing to do with thread safety.
If you are writing single-threaded code, keep in mind that some day you or somebody else may need to use it in a multi-threaded environment. Therefore most of the hints above apply to some extent to single-threaded programs as well!
More on the shape of the Universe
I one of my previous posts I postulated that the Universe does not have a 3-dimensional shape, but rather is interconnected with itself in all directions as if it was the surface of a 4-dimensional sphere. The more I think of it, the more it makes sense.
Many people believe that the Universe looks like a three-dimensional, expanding sphere. Before the Big Bang (or Big Bounce) the Universe was all in one spot, then suddenly it started expanding. The problem with this is that this indicates that there is an expanding boundary of the Universe, a shock wave, and that there is an edge. This creates a problem of what lies beyond this boundary. Also the conditions at the boundary would have to be different from conditions deep inside of the Universe, due to the interaction with the outside. I wonder what effect would gravity have on the outlying galaxies. One could argue that since the speed of the expansion is greater than the speed of light or gravitational waves, there would be no difference.
The speed of the expansion of the universe has been reaffirmed in a recent study to be about 73km/s per megaparsec. The farther the object from an observer, the quicker it is escaping. So objects which are two megaparsecs from are escaping at 145km/s from the observer. One could argue that because of this it is not possible to see what is outside of the universe, because to get there one would have to travel faster than light. If the Universe was a three-dimensional sphere, there would be galaxies very close to the boundary. An observer from such galaxy could potentially reach the edge of the Universe without exceeding the speed of light and see what’s outside. Unless the laws of physics were different at the edge of the Universe and for example expansion was faster over there. But so far we found no such evidence and the escape velocity seems to be proportional to the distance from us.
However if the Universe is “closed” and has no edge, no single most outlying point, then nothing can escape from it, there is no energy sink. There is no place in the Universe where one could exit it using conventional means and see it from the outside. There is no outside. This is mind-boggling, but I think it has more sense because it avoids the problem of an infinite space outside of the Universe and possible conditions outside.
Again, in a “closed” Universe one could potentially travel in any given direction in three dimensions in a straight line and would ultimately arrive back at the starting location. In practice, however, this is not testable, because the escape velocity of more distant objects is greater than the speed of light. In fact we can’t even see the entire Universe, we can only see a portion of it, so we can’t even see Earth from very distant times. At least that’s what we think…
What’s on TV?
I don’t have broadcast TV reception at home. In fact I only listen to the radio in my car and only on the way to or back from work. That’s like maybe 20 minutes a day tops, on a good day.
It goes like this: I’m stopped at the red light and getting bored or I’m coming back from work and my head is almost exploding from thoughts banging around inside. To ease my mind I turn on the radio. These are the things I hear:
The most common are commercials. When I hear a commercial I just switch to another station. The next station often also has a commercial, so I keep going until I find one which doesn’t, or I turn the radio off.
The next common thing is music I hate. Typically these are the so-called “hits”, i.e. music which someone in a record label decided to promote. I have no idea how people can listen to most of this kind of stuff, it’s usually loud BOOM, BOOM and a woman screaming out her lungs or some tune which is so annoying that I switch the station before I hear the chorus.
There are specialty stations which only play one kind of music. They are a nice change on the first few listens, they usually play more music than commercials and they don’t play the usual kind of trash than most stations do. However these stations get annoying after a few weeks, because they are playing the same things over and over again. How many times in a row can you listen to the same old song? Even though I listen to any kind of station at most 20 minutes a day, so that’s even much less per station, I can tell that they are repeating their stuff, so their selection of music must be really low! Take the music collection on your favorite pocket device, how often will you hear songs repeat if you listen only to 5 songs a day?
Sometimes its fun to listen to foreign language stations, for example it’s easy to tune to some Mexican station in the US. The Mexican songs are fun from time to time but they are also all written to the same kind of melody and they are also all about a broken corazon – I challenge you to find a song in Spanish which does not have the word corazon in it.
Back to TV. I do watch broadcast TV a few hours a year, for example when I’m in a hotel. Every time I watch TV it reminds me why I don’t have it at home – there is nothing on it. You can have hundreds of channels, and none of them has anything interesting. Sure you can laugh at some sitcom once in a while, but that’s it. OK, maybe you can find some interesting series from time to time – but then it’s interrupted every 5 minutes with very long commercials. So out of a 40 minute show they can easily make a one hour show. If you really like some show, then you need to remember to be at home ready at exactly the time they have it, otherwise you will not be able to watch the whole thing. If you have extra money to throw away, you can get a DVR, but the commercials remain.
The Internet to the rescue! Fortunately there are streaming services now, so you can watch whatever you want, whenever you want/can and without commercials. And it’s inexpensive. I don’t know why people still watch broadcast TV at home.
Internet radio is nice, but it’s not available in my car, plus it’s also been crippled with commercials in the recent years. There are paid options, but I don’t spend enough time in my car to want to pay for that.
How long before broadcast TV and radio share the fate of dinosaurs?
The source of all hatred
Recently I’ve read an interesting article in a well-known magazine about the evolution of cooperation. The bottom line of it was that cooperation evolves together with competition. It makes a lot of sense and can be seen in many species, including humans.
Competition is good, because it promotes individual good features. This way the good features spread among a species. This way the whole species can adapt to a changing environment.
On the other hand cooperation is also good. Those who help each other make it easier for their group to survive, while those who are selfish have it harder, so obviously the ones with more altruism have more chance to survive, thus the altruistic features spread better. Obviously individuals in any given group share more physical traits with each other than with individuals from other groups, so helping individuals from the same group or family helps the same or similar genes to survive. In some species it does not matter too much, e.g. tigers live solitary lives. Other species are on the other side of the spectrum and seemingly rely on almost total devotion, such as ants.
All species evolve together with a balance between competition and cooperation. It’s hard to say arbitrarily what the balance is for each species exactly, but it is certainly different between various species and depends on their traits and environments – apparently competition is more important for tigers and cooperation is more important for ants. One could determine clues on why this is, but it’s not important here.
So what struck me in humans is that cooperation leads to promoting and supporting their own groups. For example people of the same race, religion or hobbies, etc. tend to stick together in order to cooperate. But at the same time they may be competing with other groups. This is rooted deep in human nature and goes back way before tribal groups, back to apes. Chimpanzees share similar behavior, while they cooperate within their groups, they sometimes fight between groups. So while cooperation makes us like people similar to us, competition makes us hate others who are different from us.
When you look at it from this angle, it explains the existence of many of the bad human features, such as racism, hatred, etc. They are rooted in humans and were one of the primary tools of human evolution. On one hand the good features such as altruism helped humans survive as a species in their environment, on the other hand the bad features which were helping promote individual genes, were the result of competition.
Humans are getting less aggressive these days and due to globalization and cheap travel they and their cultures mix. Eventually there will only be one group.
Next time you see hatred, don’t ask where it’s coming from, think of this post.
Evolution
Most people consider evolution just a proven biological theory which explains biodiversity and how humans came to be.
But I think of it in a different way.
I don’t know if you’ve heard of meme theory. In my definition a meme is any cohesive set of information which together makes a whole. Examples of types of memes include stories, books, gossips, religions, computer programs, food recipes, designs (mechanical, architectural), movies, songs, etc. A notable example is of course information encoded in chromosomes about an individual organism.
Memes are copied very easily. For example stories are told and repeated, books get revised, movies get remakes, designs get fixed and improved, creatures reproduce, etc.
When memes are copied, they are also often modified for whatever reason. Sometimes on purpose, sometimes because of errors. When you look at a history of a meme, it will look like a graph. Multiple copies may be modified in different ways. In time the meme changes.
This is evolution.
So in my definition, evolution is change which happens to any kind of memes or information over time. This change is inevitable. Even if there is no practical need to change memes, they often change due to errors resulting from the imperfectness of the medium (such as human memory, errors when copying genes, etc.)
To many programmers this is no news, since “genetic algorithms” are very useful in searching enormous parameter spaces for local maxima.
Evolution is everywhere and governs the change of everything.
Rewrite from scratch?
One day we’ve decided to import a piece of code of a significant size from another project. It made perfect sense and allowed us to avoid spending months to write what others have already written. This happens quite often in many projects, because code reuse saves time and money.
After making it work, days later we’ve discovered saddening truth. Lots of resource leaks! The source project was sloppy with resources, because it did not matter much in that particular project and perhaps they don’t have the right tools to even know about the resource leaks’ existence.
A few hours spent with a leak checker revealed that even though the code was written in C++, it was written in a C-like fashion, with objects allocated directly with new and stored in raw pointers without ever being released. Some containers were semi-hand crafted, though they used STL containers underneath, but holding raw pointers.
Lots of programmers given such code would scream: “Rewrite from scratch!”. But is it really such a good idea? I don’t think so. I don’t doubt that there are projects which absolutely need a rewrite, but in many cases refactoring comes to the rescue. In the end refactoring is a less costly alternative. If there are tests for the original code (hopefully!), the approach is to slowly fix the code. In this particular case the first thing is to gradually introduce the right resource allocation and management mechanisms which are not prone to leaking.
The size of the task of importing foreign code is hard to estimate. One of the reasons is that taking code from one project and putting it in another, new environment will make the code behave differently enough to reveal obscure bugs. On the other hand if that code remains maintained and shared between projects then its quality will improve. So everybody can benefit from reusing, and if needed refactoring and fixing existing code.
Prometheus (2012)
Prometheus is yet another sequel to a popular series, Alien(s). The movie is actually a prequel of the original Alien (1979) movie. While previously every Alien movie had a different director, this one is directed by the same person as the original Alien, Ridley Scott.
The story is placed before Alien and the ending blends quite well with Alien. I watched Alien long ago, so I checked out its screenshots on the web and it seems the Prometheus team took the original spaceship concepts which we could see in Alien and reused them. The spaceship looks similar in both movies, both inside and outside.
The movie does not attempt to be as scary as Alien. There was one or two jumpy scenes, but that was it. It’s actually good, since I was expecting a good SciFi instead of just a horror.
Prometheus explains the existence of the nasty alien creatures, although it (fortunately) bears no connection with the B-movie Alien vs. Predator, which was silly IMHO.
The plot evolves around a scientific expedition trying to find origins of human civilization. The flick tries to have a deeper meaning, by exploring the questions of existence and life creation, god, and alien civilizations.
If you’ve seen any of the Alien movies and liked them, I strongly recommend seeing this one. It’s very well made, excellent piece of SciFi. There is a lot of action in it and no boring moments.
Spoilers
Nowadays there is a “creationism” movement in the US, which tries to enforce new laws of teaching that god created life on Earth and that evolution is “just a theory”. Prometheus seems to be aiming at that. The message of the movie is that humans are neither a creation of god nor evolution, but rather direct descendants of an alien species. The first scene in the movie is the creation scene where an alien being throws itself from a rock into water to seed the Earth with its DNA.
Although the movie is quite clear about it, the ending leaves the interpretation slightly open – people who believe in god will be able to say that there must be god after all, since the only person who survived was a deep believer. I don’t know if this was intended, I suspect that the studio wanted this to satisfy a broader audience. This is what I didn’t like about this movie.
There are several things in the movie which don’t make scientific sense, such as the abovementioned indication that humans descendent from aliens, gravity on the ship and on the alien moon seemingly the same as on Earth, the aliens growing in several hours without eating a lot of food, etc. But it’s fun to watch regardless.
The thing I liked the most is that the vicious alien creatures turned out to be an engineered biological weapon. This makes a lot of sense, because I don’t believe that an alien species could evolve the capabilities of surviving in so many environments and eating humans.
Would I watch it again? I will!
What’s the magic word?
Apparently cracking a 11-character password with lowercase letters and numbers plus a single symbol takes under 3 weeks if you have a lot of computing power.
If you only have a few powerful computers it will take 54 years.
I think the author forgot to add that it will take 54 years “using today’s technology” and did not adjust for the fact that the computing power doubles every 18 months. This is still true for GPUs and CPUs may start improving like this again in a few years with manycore architectures. One may argue that we will eventually hit a wall once we get down to a few molecules, but there’s still quantum computing and optical computing to explore, so computers will keep getting faster in the years to come.
It looks like no password is safe.
Most common source of bugs
There is one single source of most bugs. It’s obvious, yet almost nobody talks about it. That source is statistics.
You can call it a stretch, but it’s true. No matter how you classify a bug, whether it’s a race, a leak, whether a programming error, a typo or a misunderstanding, statistics influences whether that bug occurs or not in the first place.
Using mallocs/frees all over the code or using lots of gotos is not a source of bugs per se. Most occurrences of constructs widely perceived as bug prone will not produce an incorrect program. Until these constructs meet statistics.
If we put it this way, it sounds hopeless, because statistics quantifies everything around us, every programming technique. But we can use this fact to choose which programming techniques we use or even as far as which programming language we use, to reduce the number of bugs.
Using the above example, if we write a program explicitly calling malloc() and free() to allocate and release memory as needed, we will occasionally forget to call free() and introduce a memory leak in the code. In C++ the simplest solution to that is to never use free() or the delete operator, but to rely on destructors to do their job instead (e.g. the use of std::vector or std::make_shared() in C++11, etc.). This way we will never forget to free memory, the compiler will do this for us.
Chris Dragan's Corner 