Archive

Archive for October, 2012

Writing

29.10.2012 Leave a comment

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.

Advertisements
Categories: Other

Multithreading

16.10.2012 Leave a comment

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!

Categories: Computing

More on the shape of the Universe

11.10.2012 Leave a comment

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…

Categories: Universe