Feeds:
Posts
Comments

Posts Tagged ‘Foreign Function Interfaces’

When working on some code, I came across a random number generation algorithm (a pseudorandom number generator to be exact, since the numbers aren’t truly random but only designed to “look” like it to the casual observer) called ISAAC. The name stands for “Indirection, Shift, Accumulate, Add, and Count,” which is essentially what it does to a set of state variables, in that sequence.

The algorithm allows sequences of 32-bit numbers to be generated extremely quickly, since the operations it uses are relatively fast on modern processors; in fact, the author, Bob Jenkins, claims it only requires (on average) 18.75 machine processor cycles to generate each 32-bit value.

Even so, the algorithm is designed to be as uniformly distributed as possible.

I decided to test how fast this would be on a relatively modern multiprocessor system. The following is a benchmark on an amd64 machine with 2GB of memory. The benchmark script is available as part of the Math::Random::ISAAC package available via CPAN or its SVN Repository.

Rate ISAAC
PP
MT ISAAC
XS
Math::Random TT800 Core
ISAAC::PP 134/s -54% -79% -82% -90% -98%
MT 292/s 118% -53% -61% -78% -95%
ISAAC::XS 626/s 367% 114% -16% -54% -90%
Math::Random 748/s 458% 156% 19% -45% -88%
TT800 1350/s 907% 362% 116% 80% -78%
Core 6211/s 4534% 2024% 892% 730% 360%

So as we can see, Perl’s built in rand() function is evidently really, really fast; quicker than every other algorithm studied here by a few orders of magnitude. What remains to be seen, then, is whether the quality of random numbers actually generated is any good. Ideally, most random number generators are designed to produce distributions of numbers that are uniformly distributed — that is, every number is equally likely to occur.

Uniform distributions often do not occur in real-life “random” samples – for example, things like height or marks in a class tend to follow more of a normal distribution (or “bell curve”) – the majority of the sample population is near the mean, and it drops off as you go to higher or lower figures. Nonetheless, these types of random numbers are great for uses in computer science — where you want each number to be equally likely, thus ensuring that your sequence is as unpredictable as possible.

In this case, all of the algorithms produce relatively uniform distributions, though the TT800 and Perl rand() core function produce a somewhat jagged distribution. Less interesting distributions are those for ISAAC, Math::Random and the Mersenne Twister.

Advertisements

Read Full Post »

As some of you know, I’ve applied to this year’s Google Summer of Code (GSoC). In particular, I am interested in working with the Debian project, but my proposal has impact in a few other communities, including KDE’s Qt project and Perl.

Every year, Google provides students with a $4500USD stipend to work on an open source proposal that they submit. Additionally, they provide $500 to the organizations that mentor students.

Last year, there were 1125 students/proposals accepted for the Google Summer of Code, which means that Google was prepared to invest over $5M in the development of open source software, the development of which does not directly benefit them. I don’t know about you, but that sounds like a pretty good case of “Don’t be evil” to me.

My proposal is mainly on two fronts:

  1. The Debian control files are the backbone of Debian’s package system. Each package has a file that describes things like dependencies, so that tools like APT and Aptitude can use them to provide access to a rich package-based repository of software. Part of my proposal involves providing a programmatic interface for handling these files, which I’m told sounds like a boring task. That might be true, but the huge positive ramifications it has for my favourite operating system are compelling enough for me to want to work on it.
  2. Perhaps more interestingly is the K Desktop Environment, which is a project to provide a pretty easy-to-use graphical interface for Linux. Along with this is a toolkit for creating applets called Qt (and indeed, the resulting interfaces are cuties). One of the problems for Debian though is no complete implementation of a Perl interface to this toolkit, which is something I hope to change.

While the second task looks a bit scary at first (since I don’t know anything about KDE4 or Qt4 yet), I’m confident my experience playing with foreign function interfaces in Perl using XS will reduce the learning curve substantially.

I’m quite anxious to find out the results. My project is one of twelve that have been shortlisted by the Debian GSoC people as projects that they would like to see funded. If you’re bored or otherwise interested, you can read the full text online. The results will be published and announced on April 20th at some point, so I’ll be getting increasingly nervous as we get closer to that date.

Read Full Post »