A binary search is not a very interesting topic as it is a well known and fairly simple algorithm. However, I have encountered an interesting variant of it lately – one that I would like to share.
The Linux Kernel defines one Jiffy as the period of time between two consecutive system timer interrupts, and keeps a “jiffies” counter. Having jiffies, the next handy parameter would be the amount of delay-loop iterations that the CPU is able to fit in a single jiffy. With this number at hand (and known timer frequency) the kernel is able to support fine-grained execution delays, for instance. How would you implement computation of said “loops_per_jiffy” parameter?
Continue reading Bitwise binary search
Every programming language has its benefits and its drawbacks. Python, for example, provides a dynamic and clean environment for the developer, which boosts productivity by hiding much of the “dirty work”: memory management, type inference (duck typing, in this case), and more. Such benefits usually come at the cost of efficiency, which is something that other programming languages (such as C++) excel in.
The next logical step would then be a way to combine the benefits of such different programming languages in a single system. For instance, we could use C++ solely for the cpu-intensive parts, while the rest of the software could very well be written entirely in Python. The missing piece would then be a way to integrate the two. The common way of doing so is through SWIG, which is a tool that is able to wrap C++ to many different programming languages, Python included. Using SWIG right out of the box, we will be able to invoke C++ code directly from a Python interpreter. But what if we wanted to extend C++ classes in Python, making native C++ seamlessly call Python code?
Continue reading Python directing C++
A few months ago I have been to the states. Naturally, one big outcome of that trip was a handful of photographs documenting it – 1.6GB of these, to be precise. The bad part is that I have forgotten to reset the camera settings beforehand, which made all the pictures date a few years back.
The images I made with my Cannon camera (sx110) use JPEG for compression, and Exif for the metadata – including the date and time the picture was taken, which is what we’re interested in. Being as perfectionist as I am, and having some familiarity with Python, I set out to modify the metadata on the pictures to contain the right dates for the trip.
Continue reading Fixing incorrect photo data
Writing fairly straightforward C++ code, we usually make heavy use of the RAII concept. Therefore, we greatly rely on the simple (and basic) assumption that all appropriate destructors will be called. What happens if that is not the case?
Continue reading Unexpected skip of a destructor
A priority queue in the STL is nothing more than a regular (maximum-) heap. It is essentially an adapter built on top of another container, usually a vector. Therefore, the offered priority queue can easily contain an arbitrary number of elements (so long as memory permits).
But what if we wanted to keep only the biggest N elements, and just have the queue dynamically throw away all other elements? I am sure you can imagine why such a behavior would be much desired: for instance, keeping the best N suggestions for a specific search term springs to mind. Unfortunately, the STL does not support such an adapter.
Continue reading Bounded size priority queue
Generic programming is very common and has different names (and features) in various programming languages; C++ provides Turing-Complete Templates, Java offers Generics (along with Ada, Eiffel, C#, and Visual Basic .Net), and Parametric Polymorphism is present in ML, Scala, and Haskell.
While I am generally pretty happy with what C++ has to offer, adopting some of the features offered by other mechanisms can come in handy sometimes. To be more specific, in this post we will mimic Java’s support for defining a common super-type for generic elements (i.e. List).
Continue reading Imitation of Java Generics
Using the initialization list is very much encouraged in C++, and rightfully so – it has many benefits. But what happens if one of your members fails at initialization and actually throws an exception? Even worse: what happens if that member’s constructor throws an exception not in your exception specification list?
Continue reading Exceptional initialization list
The word thunk has at least three related meanings in computing science. A “thunk” may be:
- A piece of code to perform a delayed computation (similar to a closure)
- A feature of some virtual function table implementations (similar to a wrapper function)
- A mapping of machine data from one system-specific form to another, usually for compatibility reasons
In all three senses, the word refers to a piece of low-level code, usually machine-generated, that implements some detail of a particular software system.
In this post (whose name looks like an unrelated typo) we shall observe the need for a thunk of the second kind, in C++.
Continue reading Thunksgiving
Programming is all about generalizations. We, as programmers, usually do not want to worry about all the small details; We will usually assume that there’s enough physical memory on the machine, we will knowingly use cross-platform libraries to make the operating system we’re running on irrelevant as well, and sometimes we will even resort to using programming languages that take these ideas to the extreme – like i.e. Java, which runs entirely on a virtual machine — making all above issues non-existent.
But there comes a time, especially in low-level programming languages (like C++ luckily is), when we simply cannot ignore certain low level details. One such example is the expected, architecture specific, Endianness.
Continue reading Endianness and you
The feature of function overloading can prove to be pretty useful: it allows us to define a few versions of the same function, which differ in argument types, or even in Arity (ignoring variadic functions for the moment). Unfortunately, the C\C++ pre-processor does not allow overloading macros in the same way; It treats such attempts as redefinitions.
While we do not really need to overload a macro in order to handle different argument types (since macros ignore type information), many times it would be desired to overload a macro such that each version is able to handle a different number of arguments. This goal can actually be achieved through invocation of the VA_NUM_ARGS macro mentioned in my previous post, as we will briefly demonstrate (the idea has also been mentioned under the comment section in the aforementioned post).
Continue reading Overloading macros