söndag 18 augusti 2013

Soft Realtime Java

Anyone visiting my home could verify that garbage collection is something best left to some other entity than me. One severe problem with having a computer program looking what your program is doing trying to clean up after it, is that it sometimes gets so confused it has to trigger some divine intervention, stop the time, go through much of the allocated memory and reallocate parts not in use anymore.

This seasonally cleaning can take a while. Usually that's ok, but for more and more applications the world can't wait. One of these are when the computer is busy generating cool synth sounds for a dancefloor in real time.

To solve this issue many programs simply don't use Java, but C++ or something else where you have more control over how your memory is allocated and deallocated. This leads to nicely working software, like the Ableton Live, but also rather much work for the programmers behind it. Ok, Javas somewhat crimped primitives and the JVMs limitied abilities to reach new efficient processor instructions wouldn't make much to help it out either, but anyway.

One new player in the game is IBM's Metronome GC, that can guarantee a maximum pause time for Java GC that is about 2 ms. Of course, someone made a sample-player synth written in java with rather competitive latencies.

onsdag 14 augusti 2013

Garbage Collection visualization

I really like the old disk defragmenter program in Windows. The small blocks where moved all around and I could watch it for hours (well, minutes at least).

The JVM Garbage Collection is something of a black-box which sometimes just makes everything go to halt. To get a better understanding of how it is struggling with my code I wanted something like the disk defragmenter, and, Eureka! Netflix has made their own tool, gc.viz (blogpost), and also logs all the garbage collection closely in their production systems. Interesting indeed!

lördag 10 augusti 2013

Leaderboard, some approaches

I'm looking into the leader board problem. In short, the problem can be expressed as the most efficient way to take the n best out of a large (often semi ordered) set with the size m (the cardinality of the total league).

The most naive version is to keep a list of the n≤m best players seen so far. If we assume no sorting among these n players, the complexity of the algorithm will be n*m, which is often unacceptable, since both m and n can be huge.

Cache the worst one the list
A slightly less naive way is to cache the least good player in the current toplist. This will, at best, give only slightly above m comparisions, given that the best players came first. Beware though, if the set is given in reversed order, the complexity once again soars to n*m.

Keep a binary tree heap
A heap is an often excellent way to select items out of a set. The most general selection, the heap-sort has a well known n log n complexity. The heap could be a candidate because it keeps the players on the top list sorted and could be a good candidate. This is not the case. The binary tree has the sad property that it can be very unbalanced and we are back again at n*m.

Keep a balanced binary tree heap!
Now we're talking! There are several trees that balance themselves in a well-known worst case time available. Actually, there are some specialized heap data structures availiable, a list from Wikipedia on Heap data structures gives the following
  • 2-3 heap
  • Beap 
  • Binary heap
  • Binomial heap
  • Brodal queue
  • d-ary heap
  • Fibonacci heap
  • Leftist heap
  • Pairing heap
  • Skew heap
  • Soft heap
  • Weak heap
  • Leaf heap
  • Radix heap
  • Randomized meldable heap
where the Fibonacci and Brodal heaps seems to have among the best over-all performance (edit: no, the different heaps do of course have different properties depending on the insert/delete proportions). 

I'll give a try to implement the Fibonacci heap. And yes, it's one availiable in clojure already, courtesy of Mary Rose Cook, maryrosecook/fibonacciheap, built with zippers, nicely described a great blogpost. Super elegant.

fredag 9 augusti 2013

Small app for finding BPMs by key-tap

With Giorgio-voice: When I was young, 15-16 I definetly wanted to become a DJ and producer. I left that for my friends in Skillnicker instead. I took the engineering route instead. And here we are.

When you want to mix two songs togheter they needed to be in the same tempo, therefore we marked our records with the number of BPMs a certain song had. We calculated in the beginning by measuring the length of 16 beats with a stop watch and look into a table. After a while there were programmes where one just could tap the space bar and get a decent result. Here is such a program in Clojure.

  The intresting part of the program is the minimal state, it's just the last time we got a key press in the frame. I will add a Kalman-filter to it soon, giving it a state of a hefty two or three variables.