yuri:design:notes [projects.iim.cz]

Design notes

This page contains notes abou implementation details in current or previous version of libyuri, design of 3.0 should be on separate page.

Container for planes

From version 2.0, the planes were stored as a std::vector of shared_ptr's to the class BasicPlane<T>, that was wrapping boost::shared_array<T>. As I'm trying to remove dependecy on boost from the core library (so v3.0 could have core dependent only on c++11), I had to abandon shared_array and look for alternatives.

The most obvious STL replacement was std::vector<T>. The biggest issue with using std::vector was the fact that it initialized the values inside. This is perfectly correct and desirable for classes and general store, but for our purpose it was a bit inconvenient. Having the vector initialized is nice, but it comes at quite high price during creation/resize.

There's no replacement in current (C++03) STL, so I decided to create own class (yuri::uvector<T>) that would have the same interface as std::vector, but would internally work with uninitialized storage.

In order to support the reasoning about allocation price, I conducted testing, for type T=uint8_t (which is used as yuri::ubyte_t in libyuri) with following results:

Container	Operation	Approx. time (1000 iterations)
Creating container
shared_array(new T[size]);	Allocate array	0.5 - 0.7 ms
std::vector(size);	Allocate array	320ms
std::vector();resize(size);	Allocate with resize	320ms
std::vector();reserve(size);	Allocate (but not initialize)	0.05ms
uvector(size);	Allocate (uninitializd) array	0.05ms
uvector();resize(size);	Allocate array using resize	0.05ms
uvector();reserve(size);	Allocate array using reserve	0.05ms
Creating container and filling with values
shared_array(new T[size]);std::copy()	Allocate and copy array	530ms
std::vector(size);std::copy();	Allocate and copy array	792ms
std::vector();resize(size);std::copy()	Allocate with resize and copy	793ms
std::vector();reserve(size)insert();	Allocate and insert	478ms
std::vector();reserve(size);assign();	Allocate and assign	4775ms
uvector(size);std::copy();	Allocate and copy array	540.8
uvector();resize(size);std::copy()	Allocate with resize and copy	542.7ms
uvector();reserve(size)insert();	Allocate and insert	539.5ms
uvector();reserve(size);assign();	Allocate and assign	539.0ms

The testing array had 5MB and the test were conducted 100000x. Conclusion: uvector beats std::vector when it comes to simple creation (as expected) and it's performance for different variants of copying is similar. There's more than 10% speedup in std::vector when copying data compared to uvector.

Using uvector instead of shared_array seems to give faster creation (no reference counting here) and the copying performance is basically the same. std::vector would be even faster, but the creation times are just to high. Using vector with it's capacity only allocated (using reserve) is UB, so we definitely want to avoid that.