The Cutest Littlest Forkbomb

February 24, 2015

In one of his last tweets @levans posted the cutest Rust-lang fork bomb:

fn main(){std::thread::spawn(main);main()}

at 42 characters longs, which he sees like a sign. Excluding headers, you can do even shorter in C++:

main(){boost::thread x(main);main();}

It’s not really a terrifying forkbomb (as Linux, for e.g., kills everything after a while because processes run out of memory), and we could have done much worse with a process-level (rather than a thread-level) forkbomb:

main() { fork(); main(); }

This variant creates separate processes… none of which individualy can exhaust its memory! Don’t try this one on your main box (but it could be fun in a virtual machine).

bobomb


Of tails.

November 25, 2014

In a previous post, I explored the effect of pruning on a recursive function, namely, the Collatz function. Richard (see comment) asked “does your compiler know about tail recursion?”. Well, I didn’t know for sure. Let’s find out.

tail-recursion-small

Read the rest of this entry »


Yet Another Square Root Algorithm (part II)

May 6, 2014

last week, we saw that we could use a (supposed) efficient machine-specific instruction to derive good bounds (but not very tight) to help binary search-based and Newton-based square root extraction algorithms go faster. Last week, we saw that the technique did lead to fewer iterations in both algorithms.

malevich-square

Now, does the reduced number of iterations translate into actual, machine speed-up?

Read the rest of this entry »


Yet More __builtins

January 21, 2014

So last week we saw how to use some of GCC’s built-ins, this week, let’s have a look at how we can create our own, if need be. Say because you need to have access to some instruction and that GCC does not offer the corresponding built-in.

coin-reverse-small

To do so, we’ll use a bit of the C preprocessor and GCC’s inline assembly extension.

Read the rest of this entry »


More __builtins

January 14, 2014

Last week we discussed GCC intrinsics a bit. This week, let’s have a look at what kind of speed-ups we can get, and how the use of intrinsics affect code generation.

coin-obverse-small

Sometimes, I do strange things. I mean, my experiments aren’t necessarily self-evident, and sometimes, I need performance from primitives that usually are not bottlenecks—such as computing the GCD. This time, I need to get k and b in n=2^k+b as fast as possible. Let’s have a look at how intrinsics help us.

Read the rest of this entry »


GCC Built-ins

January 7, 2014

In the discussion of The Speed of GCD, Daniel Lemire remarked that one could use the compiler-specific intrinsic function __builtin_ctz to get a good speed-up on binary GCD. That remark made me look into all the others intrinsics and built-ins offered by GCC.

amonite

Let’s have a look to at least a few of them!

Read the rest of this entry »


Enumerating 32 bits Floats

November 5, 2013

This week, let’s go back to (low level) programming, with IEEE floats. To unit test a function of float, it does not sound unreasonable to just enumerate them all. But how do we do that efficiently? Clearly f++ will not get us there.

Buoys_1

Nor will the machine-epsilon (the std::numeric_limits::epsilon()) because this value works fine around 1, but as the value diverges from 1, the epsilon basically becomes useless. We would either need a magnitude-dependent epsilon (which the standard library does not provide) or a way of enumerating explicitly the floats in increasing or decreasing order (something also not provided by the standard library). Well, let’s see how we can do that

Read the rest of this entry »