Syntax highlighting

Looks like I finally have syntax highlighting... thanks to this!
Turns out the previous link worked only for Java and XML and I'm too lazy to compile my own version for supporting other languages, so I'm now resorting to google-code-prettify. To make it work here, I followed this tutorial.
I didn't quite like the default style as I wanted line numbers for every single line. Also, I didn't want it to have a completely white background, so after linking the default CSS file, I overrode some styles:

<style type="text/css">
pre.prettyprint, code.prettyprint {
        background-color: #C4C4C4;
}
li.L0, li.L1, li.L2, li.L3, li.L4, li.L5, li.L6, li.L7, li.L8, li.L9
{
    background: #F7F7F7;
    list-style-type: decimal;
}
</style>

Java example:

public class SyntaxHighlighterWorksFineHere
{
    public static void main(String[] args)
    {
        System.out.println("Yes!");
    }
}

In order to avoid to having to place the script loading line each time, I just added it to the HTML template. Et voilà!

Installing gevent

If you're a Python noob like me, installing gevent is not trivial. In my case, I'm using Ubuntu 10.04. These are the steps to follow:

1. Install libevent package (apt or synaptic)
2. sudo easy_install greenlet
3. sudo easy_install gevent
4. ldconfig
5. test that 'import gevent' and 'from gevent import socket' work.

Step 4 was necessary in my case since step 5 wasn't working, but you may try to see if it does in your case.

Now, I was interested specifically in the datagram server. At the moment of writing this, the release version of gevent was 0.13.6, which didn't include it, so I had to perform a check out of the latest version in the repository.

However, I didn't want to install it as I wanted to be able to switch between different versions or easily move a setup to another computer. Therefore, I wanted to manually build it into a given directory. For this, I had to do a few more undocumented steps:

1. sudo easy_install cython
2. (in gevent root folder) python setup.py build, which generates a build in build/lib.linux...
3. In my Eclipse project, link the build folder as an external library source.

Now, I wanted to be able to execute my project without eclipse... so I added a main file which set up the paths:

...

GEVENT_PATH = "../gevent/build/lib.linux-i686-2.6"

import os
import sys

# append paths to PYTHONPATH
sys.path.append(os.path.abspath(GEVENT_PATH))

# begin importing and using gevent!

...

And finally... that was it!

Installing Ack on Windows

Ack is a great command line grep alternative. In order to install it on Windows, follow the instructions here:

http://blog.thecybershadow.net/2010/09/12/color-grep-for-windows/

Vertex throughput on modern GPUs

I've read that the optimal number of triangles in order to maintain 60fps that the GPU can process is something between 1500 and 4000.

Found this interesting link:

http://nuclexframework.codeplex.com/wikipage?title=PrimitiveBatch&referringTitle=Nuclex.Graphics

But according to this presentation about nvidia http://origin-developer.nvidia.com/docs/IO/8230/BatchBatchBatch.pdf?q=docs/IO/8230/BatchBatchBatch.pdf, the question is not how many triangles per batch, but how many batches per frame!

Following that last link, the conclusions that can be drawn are:

- Number of vertexes per batch: whatever between 1 and 10.000.
- Number of batches per frame (CPU bound): 25k * GHz * Percentage_available_for_draw_calls/Framerate
- Bad performance at a small number of vertexes per batch could mean:
- GPU vertex engines are idle but the triangles itself could be expensive
- CPU bound --> add triangles for free!
- GPU idle: add complicate pixel shaders for free!

Krusader - easily obtain image info using GraphicsMagick

Want to get the information of an image easily by right-clicking on it and then on an 'identify' button?

1. Install GraphicsMagick
2. Open Krusader, go to User Actions and add a new action of type 'Archive'.
3. Copy paste this into 'commands': gm identify -verbose %aCurrent%
4. In execution mode, select 'execute in terminal'.

Now press on apply and you should be able to get the information of an image through this user action. A terminal window should open with the results of executing the command specified above.

Skip Lists compared with Treaps and Red-Black Trees

I implemented the skip list, which is a linked-list based data structure that has an average performance comparable to BSTs (O(log n) for insertion/search/removal). What I find amazing about this data structure is that it is REALLY REALLY easy to implement (insertion took... 20 lines?) for such good performance. Furthermore, it is a data structure that can be made concurrency-friendly without major complications as the underlying structure is just a linked-list.

References:

- http://en.wikipedia.org/wiki/Skip_list
- Lecture from MIT
- Article on MSDN
- C# implementation by Leslie Sanford

I also wanted to compare the performance of the Skip List against the Treap and the Red-Black Tree. For that, I used my own implementation of the first two and I used a TreeMap (in Java Collections) for the third.

The Skip List was initialized with log(n) levels, where n is the amount of keys we'll be inserting into the structures. The random number of levels for each inserted key is calculated by generating a new level with a probability of 0.50 each time (equivalent to tossing a fair coin each time).

The test was done by executing the attached application several times and more or less memorizing the execution times (yeah, not very scientific... but I just wanted to have a quick look) for inputs of <100000 and >300000 pre-generated random numbers. The results, in descending order (fastest to slowest) were:

Insertion:
1. Treap
2. Skip List /RB tree (depending on input size: RB-tree faster with smaller input, skip list faster with larger input)

Search:
1. Treap
2. RB-tree
3. Skip List

Removal:
1. Treap
2. Skip List
3. RB-tree

The Treap was consistently faster (actually MUCH faster, I have to say) than the other two for all three operations, which is also the result obtained by Heger (pages 67-75). The skip list's performance was 'pretty good' but didn't seem too stable (could also be that my implementation was flawed in some way), while the RB-tree looked very stable. However, the skip list was incredibly easy to implement, which is also a great factor to take into account.

As for the memory footprint, I couldn't really compare them fairly but the general impression after running a profiler was that both the Treap and the RB-Tree used less space, which is quite logical as the Skip List uses quite a bit space for the pointers.

Note: if you want to run the test yourself you should remove the calls to System.out.println, as they affect the runtimes. The Treap package is also within the attached NetBeans project so that the comparisons can be done.

Source code:

Download

Treaps

A Treap is a data structure that combines a binary search tree with the heap invariant, which means that any root node of any subtree has a higher priority than its children (with a max-heap invariant, that is).

The idea is that BSTs perform really well when the insertions are done randomly, as it tends to be balanced, so the Treap tries to simulate this randomness by assigning random priorities to the inserted nodes.

I quickly implemented insertion/removal only for the purpose of learning and haven't refactored it, so the code could probably be further optimized/simplified.

Quick notes:

- Insertion: insert key X with a random priority. Insert works as in BSTs. Once the node is inserted, 'heapify' the node with the corresponding rotations.

- Removal: the opposite of the insertion. Find key X to remove, rotate the node down (preserving the heap invariant) until it becomes a leaf or has a null child and then remove it appropriately.

Further reference:
- http://en.wikipedia.org/wiki/Treap
- C implementation by Farooq Mela: https://github.com/fmela/libdict/blob/master/src/tr_tree.c

The Treap might perform better than BSTs, Skip Lists or other balanced trees such as Red-Black Trees, AVLs, AA trees or Splay Trees. Reference:

A Disquisition on The Performance Behavior of Binary Search Tree Data Structures (pages 67-75)

Source code (netbeans project):

Download