Choices & consequences

Spent a little bit time tweaking RDE vector class again. As I already mentioned, the container itself is not terribly fascinating, there are not too many choices here. There’s another battle going on the lower level though, it’s interesting to see how an innocent instruction like_ size()_ can be a cause of a slowdown. Typically, a vector class has 3 properties it needs to keep track of: buffer properties (pointer and size), number of stored elements We can safely ignore buffer begin property - it has to be a pointer.

STL interface

As you are probably aware, game developers have mixed feelings about STL. Sure, it has advantages, it’s already there, doesn’t have to be coded from scratch, it’s standard. On the other hand, the guidelines are very broad, implementations can vary wildly. Performance/memory guarantees seems to be hard to enforce. Even if the interface is always the same, there’s enough wiggle room underneath to seriously break some applications. Take clear() method for example.

Some more benchmarks

Gave tr1::unordered_map a try, it seems to do perfectly average, nothing spectacular, nothing awful, except for predict_grow with 4 byte objects, where it’s almost 10x slower than the next implementation (that’s not an anomaly, it happens every time). I also found a bug in RDE where I overoptimized it a little bit - could result in a crash when searching for item that’s just been removed. It slowed fetch by about 3%, however later I found a way to remove some branches and sped it up by ~6% again, so final version is even faster.

EA STL released, updated benchmarks

Big weekend news were EA releasing some of their codebase source, including parts of EASTL. Given that the original EASTL document has been the main inspiration for my RDE STL experiment, I was very interested in finally seeing the code itself. First impression - it’s still big. It is leaner than STL, but it is a big library. That’s quite understandable if you remember it’s not a local, one studio thing, it’s used by the whole organization.

Catching up

Few words about what I’ve been up to profesionally for past months. As you may have heard - Geralt is coming to the consoles. There’s PS3/X360 adaptation of ‘The Witcher’ in the works. It’s being developed in close cooperation with French company - Widescreen Games. They’re cool guys, basically mix of best oldschool French sceners (like Patapom/Bomb) and game developers (including Outkast programmers). Before diving head first we had to deal with re-designing many elements of the game like combat and UI.

RDESTL - changes

Seems like I’m mainly pimping RDESTL recently, but that’s all I’ve time/power to work on when I’m back at hotel. Quick update: latest hash_map included in Attractive Chaos benchmark (+bug fixes). It did quite well. One problem is it consumes memory like crazy, but benchmark works on a really huge set. Anyhow, memory/performance ratio can be controlled via load factor parameter. I’ve added simple stack class (built on top of other generic container, like in STL).

RDESTL: hash_map, another take

I’ve been reading lots of interesting stuff on hash tables recently and was trying to improve my RDESTL implementation of hash_map. At one point I had 5 different versions, but finally managed to create something that’s good enough for most applications. Granted, I exploit the fact that performance’s the most important factor, so I can live with some limitations that wouldnt fly in any more general library. I effectively “ban” two hash values (0xFFFFFFFE & 0xFFFFFFFF) for example and use it for my own purposes.

RDESTL - fixed_list

I didnt have much time to work on RDESTL recently, but I try to commit some new stuff every now and then (usually bug fixes). One rather interesting recent addition is a fixed_list class. Basically, it’s a rough equivalent of already existing fixed_vector. It never allocates any memory and works only withing given buffer. Let’s try to create linked list of integers, that can hold up to 64 elements: rde::fixed_list<int, 64> lst; lst.push_back(5); lst.push_back(10); lst.push_front(3); It’s not the coolest feature of this class.

RDESTL - hash_map with linear reprobing

There are several approaches to implementing a hash map. Main difference is in the way we handle collisions between entries falling the the same bucket. Probably the most popular and elegant is “chaining”, where for every slot we have a linked list of entries. In case collision we just enqueue entry in list for correct bucket. Variation of this method is used for example in MSVC’s library. I implemented it in the first version for RDESTL as well, just because it was the most straightforward.

RDE STL - fixed vector, first draft

Uploaded first draft of fixed_vector class to RDESTL (well, right now it’s just a different storage type, to increase code reuse). It needs some cleaning up and I’m not really satisfied with the shape of final interface for the moment, but the general idea seems to work. Basically, it’s exact equivalent of vector class, but all the memory is allocated statically on the stack. Capacity is generally fixed and shouldnt really grow (TODO: add methods to record watermarks).

RDESTL - string class

Copy-on-write behavior of the string class is implemented as policy now as it may or may not be desired. I’ll add “standard” storage policy as well, so it can be easily switched between. Old comments sconosciuta 2010-04-01 03:24:27 […] new products and limited editions of international brands as well as independent ones. We…RDESTL string class | .mischief.mayhem.soap.Copy-on-write behavior of the string class is implemented as policy now as it may


Instead of uploading complete code package every time, I set up SVN repository for RDESTL. Click here for the latest version of the code. Progress will be a little slower now, that I’m back at work, but I managed to add first, very basic version of COW string class. Old comments admin 2010-05-15 20:00:29 Pavel: Personally, never used it as a whole package and sole container/algorithm library, so more of a playground.


I’ve some days off after finishing the project, flying to warm countries for holidays soon, but in the meantime I started reinventing the wheel for n-th time. I was inspired by EASTL (Electronic Arts’ version of STL) and tried to create small subset of STL, aimed at game development. I started with stuff that I knew would be needed, I dont plan to add multiset equivalent soon :). Main goals were: simplicity/clarity true portability (STL leaves too many things to be implementation dependent to my taste, it can especially bite you in the ass when developing for consoles) memory control efficiency.