Alexander Kojevnikov | Blog

Faster Fast Fourier Transform

Spek logo Spek is already pretty fast at analyzing audio files and creating their spectrograms. Apparently, it can be made even faster!

A sizable chunk of processing time is spent calculating discrete Fourier transforms of audio samples. In this post I'm going to explore a few DFT libraries and compare their performance to what Spek is currently using.

This won't be a comprehensive overview of all available libraries. I'm going to benchmark only what Spek needs:

The list of candidates is surprisingly short:

The test setup is straightforward (the code is on GitHub in case you're curious):



As expected, djbfft is the slowest, using SIMD instructions does make things faster. I am however surprised how fast the FFTW is compared to avfft (approximately 60% faster!)

Conclusion: Next version of Spek will switch to FFTW.

Published: 2014-08-31

Tags: spek

xmonad-log-applet 2.1.0 released, with MATE support

I've just released a new version of xmonad-log-applet. Thanks to Ari Croock it now works with the MATE desktop environment, just include --with-panel=mate when configuring the applet.

Because GitHub recently disabled new downloads, the tarballs are now hosted on Google Code.

I also added a new tag for the applet in case you want to follow just x-l-a related posts.

Published: 2013-01-16

Tags: xla xmonad gnome

Spek 0.8.0 Released

Spek logo After more than a year in the baking, a new version of Spek is out!

This release is almost a complete rewrite driven by the switch from GTK+ to wxWidgets to simplify packaging and to improve integration on Windows and Mac OS X. The switch also allowed to make a singe-exe version of Spek on Windows, which was a frequently requested feature.

Spek now allows to change the spectral density range, which is essential when trying to detect lossy transcodes. It also handles the low end of the density better resulting in less noisy spectrograms.

There were also some infrastructure changes: downloads and issues have been moved from Google Code to GitHub, and wiki pages with platform-specific installation instructions have been moved to a single INSTALL file.

Read the changelog for the full list of changes in this release. Download links and installation instructions are available on the Spek homepage, get it while it's hot!

Published: 2012-09-23

Tags: spek

The Boston Hackfest

The GNOME and Mono Festival of Love was a blast! I finally met Bertrand and Aaron -- my fellow Banshee co-maintainers; as well as a lot of GNOME and Mono people. I also met Udesh, the SoC student I'm mentoring this year, who is working on voice control in Banshee.

I reviewed and committed a bunch of (mostly long overdue) patches in Banshee and taglib-sharp, and released a new version of the latter. We also discussed with Udesh his project and went through some technicalities.

I want to thank David for organising the event, GNOME Foundation for covering my plane tickets and our sponsors for making it happen:

GNOME Foundation

Microsoft NERD



Published: 2012-07-05

Tags: banshee gnome

GNOME and Mono Festival of Love

Thanks to the travel sponsorship of the GNOME Foundation, this week I'm going to Boston to attend the hackfest. I will be in Boston from Thursday evening till Sunday afternoon.

Looking forward to finally meeting fellow Banshee developers!

GNOME Foundation

Published: 2012-06-25

Tags: banshee gnome

CodeSprint 2

Last weekend Interviewstreet conducted a second CodeSprint. The event had a format similar to the Google's CodeJam: they gave you a bunch of problems and you had to program your way through as many of them as you could. There were a few differences though: the number of problems and the time given to solve them was higher (15 and 48h), they also ran solutions on their servers instead of just checking the output.

I managed to solve 5 problems and to rank 145th out of 1890 contestants, spending about 12h in total during the weekend. There were a few technical quirks in the process, but all in all I really enjoyed the sprint and was pleasantly surprised by the quality and the complexity of the problems.

In this post I will explain how I solved those 5 problems; it's mostly for myself, to straighten the thoughts out, as it was a bit chaotic and stressful during the contest.

If you are interested in solutions make sure to check out the official CodeSprint website, they should have them available in a couple of days.

Picking Cards

Links: problem, solution

Sort cards by their number, then take them one by one. On step n the number of ways is multiplied by the number of cards at the beginning of the deck with ci ≤ n. If this number is 0, it's impossible to pick up all the cards.

The brute-force approach is O(N2) and could be too slow. To speed it up, we keep track of the last m : cm ≤ n and start from there. As m is never decreased the overall complexity is O(N).

Coin Tosses

Links: problem, solution

On each toss we either have a head or a tail, so the expected number of remaining tosses T(n, m) = 1 + ½ × [T(n, m+1) + T(n, 0)]. We could try a dynamic programming approach, but the formula is cyclic.

However, for m = 0 the expected number of tosses can be expressed analytically: T(n, 0) = 2n+1 - 2 (proof). Add the boundary condition T(n, n) = 0 and memoisation, and you have a solution.

Fraud Prevention

Links: problem, solution

One of the company-sponsored problems. We want to normalise email and street addresses and to keep two hashes with the combination of the normalised values and the deal IDs as keys. For each key we keep a list of credit cards along with order IDs. Then we process orders one by one and check all possible cases (see the source code comments).

I found this problem a bit uninteresting for a contest -- it's tedious and, uhm, un-algorithmic. However it would probably make a decent interview questions with all its practicalities.

Subsequence Weighting

Links: problem, solution

Generalisation of the Longest increasing subsequence problem. The algorithm is very similar: take each value one by one and maintain values (and cumulative weights) of the last elements of subsequences of certain weight. After we process all values, the last element will have the maximal weight.

One complication is that we need a data structure with efficient insertion, deletion, search and traversal times. One possibility is to use a red-black tree (as implemented by std::set) and augment it so that all nodes form a doubly-linked list. Also, unlike with the LIS algorithm, each insertion can lead to many deletions (see lines 74-82).

With such a data structure, the running time is still at O(n log n).

That was my favourite question, and the one I spent the most time on, even though in retrospect it doesn't look all that complex.

Quora Nearby

Links: problem, solution

Another company-sponsored problem. A pity N was quite small and the brute-force approach actually worked. Higher limits would require a clever data structure, such as the k-d tree and would make the problem much harder and more interesting.

First we read all topics and questions and create a vector of all topics (ID and co-ordinates) and a map of topic IDs to the lists of question IDs.

Topic queries are straight-forward: we sort topics by distance (and IDs, in case the distance is the same) and print the first m IDs.

For queries it's a bit more involving: again, we sort topics by distance, then check all associated questions using our map. The complication is that we need to check all questions for topics with the same distance, and include those with higher IDs.

Please never mind the code for this problem, my solution was accepted literally 5 minutes before the contest ended, as you can imagine I was a bit in a hurry.

Big thanks to the Interviewstreet team for a great weekend!

Published: 2012-01-12

Tags: code

muspy API

muspy logo muspy is a website that notifies you when your favourite artists release new albums. muspy is free software released under GNU AGPL.

Today I'm happy to announce the availability of the muspy API. The API allows you to create and modify user accounts, to manage the list of artists you want to follow and to receive their releases.

Someone is already working on an iPhone app that will use the API, expect more news on this front soon!

Published: 2011-11-27

Tags: muspy

Improved import in muspy

muspy is a free / open-source album release notification service.

To make it easier to populate the list of artists you want to follow, muspy allows to import top artists from your account. Today this function became more flexible: in addition to getting overall top artists, it can now import most frequently listened artists in the last 12, 6 and 3 months and 1 week.

Import from

I also lifted the limit on the number of artists that can be imported from 200 to 500, and increased the number selected by default from 50 to 100.

Do you have a feature that you want to see in muspy? Let me know! Alternatively, feel free to fork muspy on GitHub and to send your pull requests.

If you are a music lover and never tried muspy before, give it a go! With muspy you will not miss an album release ever again.

Published: 2011-11-03

Tags: muspy

muspy is now free software

muspy logo muspy is an album release notification service, you give it a list of your favourite artists and it sends you a notice (by email or RSS) as soon as they have new releases.

I wrote muspy 3 years ago to scratch a personal itch -- I was spending too much time online checking if bands I'm into have something new; but was still missing many releases.

muspy was initially developed for Google App Engine, which was the hot new thing back then. In retrospect, while working with App Engine was extremely educational and a lot of fun, it wasn't a very good fit. The recent announcement on the price increase was the last straw -- I decided to re-write it in vanilla Django and to host it myself.

I'm also releasing the source code under GNU AGPL in the hope that it will be beneficial for the service and for its users.

Major changes since the previous version:

Other than that, muspy remains pretty much the same. I migrated all the data but I encourage you to go the old site at and to check if everything was migrated correctly. Please note that the old site's background processes are not running and it will be taken down in a month or two.

Now that muspy is free and open-source, don't hesitate to look at the code, tweak it and suggest improvements. Git and GitHub make it too damn easy!

And if you never used muspy before, give it a try!

Published: 2011-10-29

Tags: muspy

xmonad-log-applet for GNOME and Xfce

xmonad-log-applet is a handy panel applet/plugin for GNOME (and now Xfce) users who use Xmonad as an alternative window manager. The applet will show the visible workspace(s), active window's title or anything you send its way from your xmonad.hs.

I recently took over xmonad-log-applet maintainership from Adam Wick, and today I'm happy to announce the release of version 2.0.0.


Changes since the previous release:

To install get and unpack the tarball or clone the repo, then run:

% ./configure --with-panel=gnome2
% make
% sudo make install

Substitute gnome2 with gnome3 or xfce4 if that's what you use. If you cloned the git repo, use ./ instead of ./configure. After restarting the panel you should be able to add the applet.

Use the provided sample xmonad.hs file to bind it to Xmonad. It depends on the DBus package, which currently doesn't compile with GHC 7.x, but it's easy to work around:

% cabal update
% cabal unpack DBus
% cd DBus-0.4
% $EDITOR DBus/Internal.hsc

Replace import Control.Exception with import Control.OldException, then:

% cabal configure
% cabal build
% cabal install

After this, your xmonad.hs should compile.

EDIT: With GHC 7.4, you also need to edit DBus/Message.hsc and prepend Foreign. to unsafePerformIO.

Happy Xmonading!

Published: 2011-09-20

Tags: gnome haskell xmonad xla

Page 1 / 3 »