Yesterday I wrote about the terrible quality of the default pseudo random number generators in the C++ standard library. The article came to the conclusion they're all around terrible, and should generally be avoided, yet, it didn't provide any alternatives. Therefore, today I'll provide you with three very good alternatives to the existing generators in the C++ standard library.

• splitmix^[1]
• xorshift^[2]
• pcg^[3]

They're almost fully compliant to the standard, and should be an almost drop-in replacement for the old generators.
There is a minor change in the interface, related how the generator is seeded. To seed any of the generators, you need to pass in the std::random_device (or any class which implements operator() and returns an unsigned int) you want to use, instead of just the seed. By doing so, I can make sure each generator is seeded accordingly.

Each of these is passing both the PractRand and BigCrush test. The raw PractRand test results can be found here and the code can be found at the end of the article.

Comparison

For comparison, I've reproduced the comparison tables from the previous article. The newly added generators are highlighted in bold.

All three generators have excellent statistical quality, while having a smaller footprint and being faster. As a bonus, each of the three generators can be implemented in less than 10 lines of code, making them super easy to port to other environments or languages.

Example

Following is an example of how to generate 10 random die rolls using the supplied pcg generator:

#include <stdio.h>
#include "random.h"

int main()
{
    std::random_device rd;
    pcg rand(rd);
    std::uniform_int_distribution<> u(1, 6);

    for (int i = 0; i < 10; ++i)
        printf("%d\n", u(rand));
}

Code

Code can be found in the following gist.

More

tl;dr: Do not use <random>'s generators. There are plenty good alternatives, like PCG, SplitMix, truncated Xorshift32*, or Xorshift1024*.

A recent tweet reminded me of the <random> facilities in the C++ standard library. Having just recently studied and implemented a couple random number generators myself, I was curious how they hold up in a modern test.
From the get-go, I knew this is going to end badly, but I gave it a shot anyway.
I build a little test program, to feed into PractRand:

#include <random>
#include <stdio.h>
#include <stdint.h>
#include <stddef.h>

template<class Rand, class T>
static void
run()
{
  std::random_device rd;
  Rand gen(rd());
  std::uniform_int_distribution<T> dis(0);

  T val;
  while (1) {
      val = dis(gen);
      fwrite((void *)&val, 1, sizeof(T), stdout);
  }
}

int main()
{
  freopen(nullptr, "wb", stdout); /* only required for windows */
  run<std::ranlux24_base, uint32_t>();
  return 0;
}

The test program is printing unsigned 32bit numbers to stdout, which will be piped into the RNG_Test executable from the PractRand suite.
I compiled a single executable for each generator, and started the tests.

Results

Most of the tests were over in just a couple seconds.

The table shows after how many iterations the generator fails the statistical tests.
The earlier it fails, the worse it is. Modern PRNGs, like PCG, are known to not fail the statistical tests at all.
That's only have the story, though.
With the table above showing the statistical quality of each generator, the following is listing it's properties:

While both the 32-bit and 64-bit mersenne twister fail (mt19937 & mt19937_64) at some seemingly high amount of data (256G and 512G, respectively), they are fundamentally flawed. They're easily predictable, large (2.5KiB of state) and multiple times slower than any other alternative.

If you must use any generator from <random>, use either ranlux24 or ranlux48, the only two which showed a reasonable result in the test. At the expense of performance.

While <random> has the building blocks to build a decent generator, with good statistical quality, it requires knowledge of the domain, and is not trivial. The predefined generators didn't stand the test of time, and are weak throughout. To make matters worse, the default_random_engine often defaults to mt19937, which, while not as bad as the other choices, is neither fast, lean nor unpredictable.
There is a certain irony, that it's known that rand() is terrible generator, while everybody is fine that C++ includes almost the exact same generator (rand() is usually implemented as an LCG).

Raw Test Results

Following are the raw tests results linked, for your viewing pleasure.

• ranlux24_base
• ranlux48_base
• minstd_rand
• minstd_rand0
• knuth_b
• mt19937
• ranlux24
• ranlux48

ranlux24_base

$ ./ranlux24_base | ./PractRand/RNG_test stdin32 -multithreaded
RNG_test using PractRand version 0.93
RNG = RNG_stdin32, seed = 0xc6851f49
test set = normal, folding = standard (32 bit)

rng=RNG_stdin32, seed=0xc6851f49
length= 256 megabytes (2^28 bytes), time= 3.5 seconds
  Test Name                         Raw       Processed     Evaluation
  BCFN(2+1,13-2,T)                  R=  +9.7  p =  1.5e-4   mildly suspicious
  BCFN(2+2,13-3,T)                  R=  +9.0  p =  4.6e-4   unusual
  [Low8/32]BCFN(2+0,13-3,T)         R= +91.1  p =  6.3e-43    FAIL !!!
  [Low8/32]BCFN(2+1,13-3,T)         R= +24.4  p =  2.4e-11    FAIL
  [Low8/32]BCFN(2+2,13-4,T)         R= +12.3  p =  2.4e-5   mildly suspicious
  [Low1/32]BCFN(2+0,13-5,T)         R= +45.5  p =  5.4e-18    FAIL !
  [Low1/32]DC6-9x1Bytes-1           R=+485.8  p =  1.8e-256   FAIL !!!!!!
  ...and 117 test result(s) without anomalies

ranlux48_base

$ ./ranlux48_base | ./PractRand/RNG_test stdin32 -multithreaded
RNG_test using PractRand version 0.93
RNG = RNG_stdin32, seed = 0x13294a68
test set = normal, folding = standard (32 bit)

rng=RNG_stdin32, seed=0x13294a68
length= 256 megabytes (2^28 bytes), time= 2.8 seconds
  Test Name                         Raw       Processed     Evaluation
  BCFN(2+1,13-2,T)                  R= +28.1  p =  6.0e-14    FAIL
  [Low8/32]BCFN(2+0,13-3,T)         R=+251.2  p =  1.0e-118   FAIL !!!!!
  [Low8/32]BCFN(2+1,13-3,T)         R= +20.5  p =  1.6e-9    VERY SUSPICIOUS
  [Low1/32]BCFN(2+0,13-5,T)         R= +16.0  p =  1.9e-6   very suspicious
  [Low1/32]DC6-9x1Bytes-1           R= +49.8  p =  3.4e-26    FAIL !!
  ...and 119 test result(s) without anomalies

minstd_rand

$ ./minstd_rand | ./PractRand/RNG_Test stdin32 -multithreaded
RNG_test using PractRand version 0.93
RNG = RNG_stdin32, seed = 0x665a9f8e
test set = normal, folding = standard (32 bit)

rng=RNG_stdin32, seed=0x665a9f8e
length= 256 megabytes (2^28 bytes), time= 3.9 seconds
  Test Name                         Raw       Processed     Evaluation
  FPF-14+6/16:(0,14-0)              R=  -7.9  p =1-6.2e-7   mildly suspicious
  FPF-14+6/16:(1,14-0)              R=  -7.1  p =1-2.8e-6   mildly suspicious
  FPF-14+6/16:(2,14-0)              R=  -6.3  p =1-1.8e-5   unusual
  FPF-14+6/16:all                   R= -13.4  p =1-1.0e-12    FAIL
  FPF-14+6/16:all2                  R= +24.9  p =  2.8e-11   VERY SUSPICIOUS
  [Low8/32]FPF-14+6/16:all          R=  -6.7  p =1-4.2e-6   suspicious
  ...and 118 test result(s) without anomalies

minstd_rand0

$ ./minstd_rand0 | ./PractRand/RNG_Test stdin32 -multithreaded
RNG_test using PractRand version 0.93
RNG = RNG_stdin32, seed = 0x3b74f60f
test set = normal, folding = standard (32 bit)

rng=RNG_stdin32, seed=0x3b74f60f
length= 128 megabytes (2^27 bytes), time= 2.2 seconds
  Test Name                         Raw       Processed     Evaluation
  BCFN(2+2,13-3,T)                  R=  +7.8  p =  1.8e-3   unusual
  FPF-14+6/16:(0,14-0)              R=  -6.5  p =1-1.0e-5   unusual
  FPF-14+6/16:all                   R=  -8.2  p =1-1.5e-7   very suspicious
  FPF-14+6/16:all2                  R= +10.6  p =  1.3e-5   mildly suspicious
  ...and 113 test result(s) without anomalies

rng=RNG_stdin32, seed=0x3b74f60f
length= 256 megabytes (2^28 bytes), time= 4.6 seconds
  Test Name                         Raw       Processed     Evaluation
  FPF-14+6/16:(0,14-0)              R=  -9.4  p =1-2.6e-8   very suspicious
  FPF-14+6/16:(2,14-0)              R=  -8.7  p =1-9.5e-8   suspicious
  FPF-14+6/16:all                   R= -13.5  p =1-8.8e-13    FAIL
  FPF-14+6/16:all2                  R= +31.8  p =  5.2e-14    FAIL
  [Low8/32]FPF-14+6/16:all          R=  -4.2  p =1-1.2e-3   unusual
  [Low1/32]BCFN(2+1,13-5,T)         R=  -6.5  p =1-5.1e-4   unusual
  ...and 118 test result(s) without anomalies

knuth_b

$ ./knuth_b | ./PractRand/RNG_Test stdin32 -multithreaded
RNG_test using PractRand version 0.93
RNG = RNG_stdin32, seed = 0x2ba764e1
test set = normal, folding = standard (32 bit)

rng=RNG_stdin32, seed=0x2ba764e1
length= 128 megabytes (2^27 bytes), time= 2.9 seconds
  no anomalies in 117 test result(s)

rng=RNG_stdin32, seed=0x2ba764e1
length= 256 megabytes (2^28 bytes), time= 5.8 seconds
  Test Name                         Raw       Processed     Evaluation
  FPF-14+6/16:all                   R=  -5.5  p =1-6.4e-5   mildly suspicious
  ...and 123 test result(s) without anomalies

rng=RNG_stdin32, seed=0x2ba764e1
length= 512 megabytes (2^29 bytes), time= 10.9 seconds
  Test Name                         Raw       Processed     Evaluation
  FPF-14+6/16:(0,14-0)              R=  -6.8  p =1-5.5e-6   unusual
  FPF-14+6/16:all                   R=  -8.7  p =1-4.7e-8   very suspicious
  FPF-14+6/16:all2                  R=  +8.9  p =  4.2e-5   mildly suspicious
  ...and 129 test result(s) without anomalies

rng=RNG_stdin32, seed=0x2ba764e1
length= 1 gigabyte (2^30 bytes), time= 20.8 seconds
  Test Name                         Raw       Processed     Evaluation
  FPF-14+6/16:(0,14-0)              R= -12.8  p =1-1.9e-11   VERY SUSPICIOUS
  FPF-14+6/16:(2,14-0)              R=  -6.7  p =1-7.3e-6   unusual
  FPF-14+6/16:all                   R= -15.4  p =1-1.1e-14    FAIL !
  FPF-14+6/16:all2                  R= +44.4  p =  2.4e-19    FAIL !
  ...and 137 test result(s) without anomalies

mt19937

$ ./mt19937 | ./PractRand/RNG_test stdin32 -multithreaded
RNG_test using PractRand version 0.93
RNG = RNG_stdin32, seed = 0xadda9d07
test set = normal, folding = standard (32 bit)

rng=RNG_stdin32, seed=0xadda9d07
length= 512 megabytes (2^29 bytes), time= 3.5 seconds
  no anomalies in 132 test result(s)

rng=RNG_stdin32, seed=0xadda9d07
length= 1 gigabyte (2^30 bytes), time= 7.0 seconds
  no anomalies in 141 test result(s)

rng=RNG_stdin32, seed=0xadda9d07
length= 2 gigabytes (2^31 bytes), time= 13.6 seconds
  no anomalies in 148 test result(s)

rng=RNG_stdin32, seed=0xadda9d07
length= 4 gigabytes (2^32 bytes), time= 26.5 seconds
  no anomalies in 156 test result(s)

rng=RNG_stdin32, seed=0xadda9d07
length= 8 gigabytes (2^33 bytes), time= 52.4 seconds
  no anomalies in 165 test result(s)

rng=RNG_stdin32, seed=0xadda9d07
length= 16 gigabytes (2^34 bytes), time= 104 seconds
  no anomalies in 172 test result(s)

rng=RNG_stdin32, seed=0xadda9d07
length= 32 gigabytes (2^35 bytes), time= 203 seconds
  no anomalies in 180 test result(s)

rng=RNG_stdin32, seed=0xadda9d07
length= 64 gigabytes (2^36 bytes), time= 404 seconds
  no anomalies in 189 test result(s)

rng=RNG_stdin32, seed=0xadda9d07
length= 128 gigabytes (2^37 bytes), time= 794 seconds
  no anomalies in 196 test result(s)

rng=RNG_stdin32, seed=0xadda9d07
length= 256 gigabytes (2^38 bytes), time= 1620 seconds
  Test Name                         Raw       Processed     Evaluation
  DC6-9x1Bytes-1                    R=  -5.3  p =1-3.6e-3   unusual
  [Low8/32]BRank(12):12K(1)         R= +6116  p~=  4e-1842    FAIL !!!!!!!!
  ...and 202 test result(s) without anomalies

ranlux24

$ ./ranlux24 | ./PractRand/RNG_test stdin32 -multithreaded
RNG_test using PractRand version 0.93
RNG = RNG_stdin32, seed = 0xd8322a9c
test set = normal, folding = standard (32 bit)

rng=RNG_stdin32, seed=0xd8322a9c
length= 64 megabytes (2^26 bytes), time= 2.1 seconds
  no anomalies in 108 test result(s)

rng=RNG_stdin32, seed=0xd8322a9c
length= 128 megabytes (2^27 bytes), time= 4.6 seconds
  no anomalies in 117 test result(s)

rng=RNG_stdin32, seed=0xd8322a9c
length= 256 megabytes (2^28 bytes), time= 9.2 seconds
  no anomalies in 124 test result(s)

rng=RNG_stdin32, seed=0xd8322a9c
length= 512 megabytes (2^29 bytes), time= 17.6 seconds
  no anomalies in 132 test result(s)

rng=RNG_stdin32, seed=0xd8322a9c
length= 1 gigabyte (2^30 bytes), time= 33.7 seconds
  no anomalies in 141 test result(s)

rng=RNG_stdin32, seed=0xd8322a9c
length= 2 gigabytes (2^31 bytes), time= 65.8 seconds
  no anomalies in 148 test result(s)

rng=RNG_stdin32, seed=0xd8322a9c
length= 4 gigabytes (2^32 bytes), time= 129 seconds
  no anomalies in 156 test result(s)

rng=RNG_stdin32, seed=0xd8322a9c
length= 8 gigabytes (2^33 bytes), time= 256 seconds
  no anomalies in 165 test result(s)

rng=RNG_stdin32, seed=0xd8322a9c
length= 16 gigabytes (2^34 bytes), time= 510 seconds
  no anomalies in 172 test result(s)

rng=RNG_stdin32, seed=0xd8322a9c
length= 32 gigabytes (2^35 bytes), time= 1008 seconds
  no anomalies in 180 test result(s)

rng=RNG_stdin32, seed=0xd8322a9c
length= 64 gigabytes (2^36 bytes), time= 1920 seconds
  no anomalies in 189 test result(s)

rng=RNG_stdin32, seed=0xd8322a9c
length= 128 gigabytes (2^37 bytes), time= 3743 seconds
  no anomalies in 196 test result(s)

rng=RNG_stdin32, seed=0xd8322a9c
length= 256 gigabytes (2^38 bytes), time= 7372 seconds
  no anomalies in 204 test result(s)

rng=RNG_stdin32, seed=0xd8322a9c
length= 512 gigabytes (2^39 bytes), time= 14681 seconds
  Test Name                         Raw       Processed     Evaluation
  [Low1/32]DC6-9x1Bytes-1           R=  +4.5  p = 0.010     unusual
  ...and 212 test result(s) without anomalies

rng=RNG_stdin32, seed=0xd8322a9c
length= 1 terabyte (2^40 bytes), time= 29803 seconds
  no anomalies in 220 test result(s)

rng=RNG_stdin32, seed=0xd8322a9c
length= 2 terabytes (2^41 bytes), time= 60168 seconds
  Test Name                         Raw       Processed     Evaluation
  [Low1/32]DC6-9x1Bytes-1           R=  +5.6  p =  8.4e-3   unusual
  ...and 227 test result(s) without anomalies

ranlux48

$ ./ranlux48 | ./PractRand/RNG_test stdin32 -multithreaded
RNG_test using PractRand version 0.93
RNG = RNG_stdin32, seed = 0xd97451a6
test set = normal, folding = standard (32 bit)

rng=RNG_stdin32, seed=0xd97451a6
length= 64 megabytes (2^26 bytes), time= 2.1 seconds
  no anomalies in 108 test result(s)

rng=RNG_stdin32, seed=0xd97451a6
length= 128 megabytes (2^27 bytes), time= 4.5 seconds
  no anomalies in 117 test result(s)

rng=RNG_stdin32, seed=0xd97451a6
length= 256 megabytes (2^28 bytes), time= 8.9 seconds
  no anomalies in 124 test result(s)

rng=RNG_stdin32, seed=0xd97451a6
length= 512 megabytes (2^29 bytes), time= 17.2 seconds
  Test Name                         Raw       Processed     Evaluation
  DC6-9x1Bytes-1                    R=  +5.5  p =  5.4e-3   unusual
  ...and 131 test result(s) without anomalies

rng=RNG_stdin32, seed=0xd97451a6
length= 1 gigabyte (2^30 bytes), time= 33.1 seconds
  Test Name                         Raw       Processed     Evaluation
  [Low8/32]DC6-9x1Bytes-1           R=  +6.1  p =  3.3e-3   unusual
  ...and 140 test result(s) without anomalies

rng=RNG_stdin32, seed=0xd97451a6
length= 2 gigabytes (2^31 bytes), time= 64.6 seconds
  no anomalies in 148 test result(s)

rng=RNG_stdin32, seed=0xd97451a6
length= 4 gigabytes (2^32 bytes), time= 127 seconds
  no anomalies in 156 test result(s)

rng=RNG_stdin32, seed=0xd97451a6
length= 8 gigabytes (2^33 bytes), time= 253 seconds
  no anomalies in 165 test result(s)

rng=RNG_stdin32, seed=0xd97451a6
length= 16 gigabytes (2^34 bytes), time= 501 seconds
  no anomalies in 172 test result(s)

rng=RNG_stdin32, seed=0xd97451a6
length= 32 gigabytes (2^35 bytes), time= 1001 seconds
  no anomalies in 180 test result(s)

rng=RNG_stdin32, seed=0xd97451a6
length= 64 gigabytes (2^36 bytes), time= 2014 seconds
  no anomalies in 189 test result(s)

rng=RNG_stdin32, seed=0xd97451a6
length= 128 gigabytes (2^37 bytes), time= 4182 seconds
  Test Name                         Raw       Processed     Evaluation
  DC6-9x1Bytes-1                    R=  -4.3  p = 0.989     unusual
  ...and 195 test result(s) without anomalies

rng=RNG_stdin32, seed=0xd97451a6
length= 256 gigabytes (2^38 bytes), time= 8169 seconds
  no anomalies in 204 test result(s)

rng=RNG_stdin32, seed=0xd97451a6
length= 512 gigabytes (2^39 bytes), time= 16166 seconds
  no anomalies in 213 test result(s)

rng=RNG_stdin32, seed=0xd97451a6
length= 1 terabyte (2^40 bytes), time= 32123 seconds
  no anomalies in 220 test result(s)

More

The following is a list of architectures where certain instruction sets have been introduced first. The column "instr. set" only lists the introduced, not all instruction sets.

Intel

Only includes consumer CPUs, not Xeons or other prosumer hardware.

AMD

If you see any errors, please contact me on Twitter @ArvidGerstmann.

More

On Windows, debugger symbols aren't stored side-by-side with the executable data in the same file. They're stored in a .pdb file (short for "program database"). This is especially great if you distribute your program to end-users, but still want to be able to debug any crashes. Just keep the .pdb file somewhere save, and any crash log you get send can easily translated back into source locations.

On Linux, debug symbols are traditionally stored inside the executable, and stripped (using strip(1)) before distributing. This takes away the possibility to debug any crash, send to you from the stripped executable.

Today I discovered a neat little trick to create something resembling PDBs on Linux, by making use of objcopy(1). In our example, I already have compiled an executable a.out, which I want to distribute to my users:

$ ls -lah a.out
-rwxr-xr-x  1 woot woot 30K May  5 11:26 a.out 

As we can see, the executable, with debug symbols, has a size of 30k.

Now we extract the debug symbols into another file, using objcopy(1):

$ objcopy --only-keep-debug a.out a.out.pdb
$ strip a.out

As we can now see, our debug symbols are extracted and removed from a.out:

$ ls -lah .
-rwxr-xr-x  1 woot woot 6.3K May  5 11:26 a.out
-rwxr-xr-x  1 woot woot  28K May  5 11:25 a.out.pdb

If we now want to debug a.out, however, gdb(1) is telling us it's missing debug information:

$ gdb a.out
Reading symbols from a.out...(no debugging symbols found)...done.

We need to attach the .pdb symbols to a.out. This can be achieved by making use of GNUs .gnu_debuglink directives:

$ objcopy --add-gnu-debuglink=a.out.pdb a.out

To confirm it's working, we start gdb(1), to see whether it can now pick up any symbols:

$ gdb a.out
Reading symbols from a.out...Reading symbols from /home/woot/tmp/pdbtest/a.out.pdb...done.

Lovely! Our a.out can now be distributed & debugged with external symbols.

Summary

$ objcopy --only-keep-debug a.out a.out.pdb # extract symbols
$ strip a.out # strip away any debug information
$ objcopy --add-gnu-debuglink=a.out.pdb a.out # attach the symbols to the executable

More

The following tweet sparked my interest to investigate further into the different ways of mapping and unmapping memory on Windows, and trying to find the "best" way:

Easy gamedev improvement for a frame allocator: Uses two virtual address ranges. At the end of the frame, decommit (unmap) physical memory of the range that was first used, switch to other virtual address range, and then commit (map) physical memory to it. 1/2

— Mickael Gilabert (@mickaelgilabert) March 13, 2018

If you're familiar with the memory mapping techniques on Windows, you may skip to the benchmark and conclusion.

Mapping Memory

As a quick recap, Windows has multiple ways of mapping (allocating) virtual memory from the operating system: VirtualAlloc or CreateFileMapping.

VirtualAlloc is pretty straight forward to use, you simply pass in the desired address (or NULL, if you are fine with the decision of the OS), size (as a multiple of dwAllocationGranularity) and flags and you get back the address of the newly allocated memory region.

CreateFileMapping is a little more complicated, since it's actual purpose is to map files on disk to memory. However, if you pass in a size and INVALID_HANDLE_VALUE instead of a valid file handle, you'll get a file mapping which is backed by the systems page file. The resulting file handle has to be mapped with MapViewOfFile.

Since Windows does not support overcommitting, unlike Linux, all allocated memory, regardless of method, must always be backed by either the swap file^[1] or physical memory.

Unmapping Memory

Now that we know how to map memory on Windows, let's look into unmapping. Contrary to any logic, there are four, not just two, ways of unmapping:

• VirtualFree, with MEM_RELEASE
• VirtualFree, with MEM_DECOMMIT
• VirtualAlloc, using MEM_RESET & MEM_RESET_UNDO
• UnmapViewOfFile

Using UnmapViewOfFile is the only legal way to unmap a region mapped with MapViewOfFile, the former three ways are legal for any memory allocated using VirtualAlloc.

Benchmark

One might think that all function somewhat similar. Either of the three ways should technically only change a couple of bits in some data structure in the kernel. Apparently so, this is not the case.

Every benchmark consists of mapping the allocated region, overwriting it (using either memset or touching the first byte of the 64k region, more on that later), to make sure all of the memory is actually committed to physical RAM, and than unmapping the region again.
The cost of the pure memset operation is also benchmarked, and subtracted from all benchmarks.

Benchmarks were run on my desktop machine at home (i7 5960X, 64 GiB DDR4-2134 RAM, Samsung 960 Pro). The size of memory region used was 300 MiB (64k * 4800).

Memsetting the whole allocated region

(the "unnormalized" bar includes the cost of the memset)

Only touching the first byte of every 64k region

(the "unnormalized" bar includes the cost of the memset)

The code for the benchmark can be found here.

Further Investigation

Further investigation revealed, that MEM_RESET is lazily unmapping the pages^[2], dropping them only in the case of memory pressure, while the other ways are actively unmapping (and probably zero'ing) the memory. This would explain the difference in perceived performance.
Releasing the memory will try to "hide" the cost of zero'ing, as explained by this fantastic blog post by Bruce Dawson.

Conclusion

If the intention is to re-use the pages in the near future, prefer to mark them as unused using MEM_RESET. Otherwise, simply releasing the pages is best, and will give Windows a better opportunity to re-use pages.
In general, though, I'd advise against any method, since the performance characteristics is not suited for anything close to (soft-) realtime.

I've yet figure out a fast way, any ideas?
Tweet me at @ArvidGerstmann.

More