List-of-Lists Test

To see more JOM Software applications, click here.  

Download:

t_lol.py (v1.0)

Version History

Version 1.00, release date 2008-11-13.

  • First release
  • Tested with N82 (PyS60 1.4.3), N96-1 (pyS60 1.4.4) and E61i (pyS60 1.4.4).

Introduction

Games quite often require list of lists i.e. matrixes to save and manipulate data. There are several ways to implement such and, as a very experienced expert, I always knew exactly which way was the most efficient way.

Oh, I so hate to be wrong! Especially since I was so certain that I was right, just based on my very experienced gut feeling. Who can you trust, if not your guts?

During latest flu season I wasn't able to do much but think. So I thought about one certain game, which I have never played much, which doesn't interest me too much, but which has been huge success all over the world. There was sample code which kept crashing and which I couldn't "read" too well. It got me interested in this test sample.

This night I was recovered enough to write a small test to compare three different ways to access a single random tile inside a matrix. The result was big surprise to me, since the method I had preferred seems to be the slowest!

List of Lists

T1 is matrix based on dictionary. This is the reason, which got me interested in performance testing. I had never seen anything like that before.

a[(x,y)] = 1

T2 is the way I used to prefer, one simple list where you access a tile with calculated offset. It does have performance advantages, when you handle tiles in rows - or so I still believe :)

b[x + y*dim_x] = 1

T3 is "normal" matrix, a list of lists. I always thought it would be slow or at least not the fastest.

c[x][y] = 1

Results


E61iN82N96-1
x=10, y=20





T1: 0.015625T1: 0.000000T1: 0.000000

T2: 0.000000T2: 0.000000T2: 0.000000

T3: 0.000000T3: 0.000000T3: 0.015625
x=25, y=50




T1: 0.031250T1: 0.046875T1: 0.015625

T2: 0.031250T2: 0.031250T2: 0.015625

T3: 0.031250T3: 0.000000T3: 0.015625
x=100, y=200




T1: 0.406250T1: 0.343750T1: 0.312500

T2: 0.515625T2: 0.390625T2: 0.359375

T3: 0.328125T3: 0.234375T3: 0.218750
x=250, y=500




T1: 2.781250T1: 2.218750T1: 1.984375

T2: 3.453125T2: 2.656250T2: 2.250000

T3: 2.296875T3: 1.640625T3: 1.437500

Disclaimers

Disclaimer1: test code was not optimized at all, it's just accessing all tiles in same way. In real life, for example Unity and Mazing Days, I have optimized cases where tiles are accessed one row at a time. Random access is very common use case, but in certain type of games sequential access can be more useful.

Disclaimer2: in real life matrixes are often small and performance differences between these methods are minimal. It's better to use something which you are familiar with than to experiment blindly.