irrMap and std::map

zet.dp.ua · Post by **zet.dp.ua** » Thu Dec 03, 2009 10:51 am

After investigating the latest android ndk (1.6) i have found that there are no stl support and i can't use std::map!!!
Stlport, sti smap - they are fast, but require a lot of extra headers. What to do? My thoughts was that irrMap couldn't be better than std::map, because...because it is std.
But after some tests i was very surprised - for my tasks (bitmap fonts, map-based message dispatching, content system storages) irrMap is faster than std::map!!!
Here are some tests (vc++2008express, intel c2d 2,6G, map<int, int>).

clear, insert, delete
100 elements:
std: 1229189
irr: 622011
1000 elements:
std: 16014869
irr: 14442909
10000 elements:
std: 199120935
irr: 1919336783
100000 elements:
std: 2932736456
irr: 300168291319

clear, insert, access
100 elements:
std: 1082107
irr: 804661
1000 elements:
std: 12795549
irr: 11685323
10000 elements:
std: 177972561
irr: 162025487
100000 elements:
std: 3586182834
irr: 3435549871

[] access
100 elements:
std: 328302
irr: 293917
1000 elements:
std: 3809962
irr: 3308409
10000 elements:
std: 55294187
irr: 46610291
100000 elements:
std: 1362508251
irr: 1015458639

iteration
100 elements:
std: 29068
irr: 21385
1000 elements:
std: 308269
irr: 268840
10000 elements:
std: 3307954
irr: 2820844
100000 elements:
std: 55698812
irr: 52914264

Irrlicht is great engine in everything!!!

Brkopac · Post by **Brkopac** » Thu Dec 03, 2009 10:57 am

Arbitrary numbers are arbitrary. Could you post your source for your test?

zet.dp.ua · Post by **zet.dp.ua** » Thu Dec 03, 2009 11:40 am

Sure. But i have modified irrMap a liitle to make it std friendly in some parts, so
http://www.filefactory.com/file/a1f8968 ... p_test.zip
http://www.2shared.com/file/9656794/564 ... _test.html

aanderse · Post by **aanderse** » Thu Dec 03, 2009 2:54 pm

Please correct me if I'm wrong but the irr map is not sorted. The stl map is:

Internally, the elements in the map are sorted from lower to higher key value following a specific strict weak ordering criterion set on construction.

They aren't equivalent data sets and therefore comparing them in a directly like that isn't really worth while.

But I don't really know what I'm talking about here, someone who has actually worked on an stl implementation (whomever that could be) could have comments more worthwhile than mine.

zet.dp.ua · Post by **zet.dp.ua** » Thu Dec 03, 2009 4:22 pm

Who told that the irr map is not sorted? Unodered (unsorted) tree is useless for searching!
irrMap implementation is based on rbtree (as well as stlport and msvc implementation). And without intensive deletions is faster. For me typical usage scenario is: insert at loading, find/iterate while playing, clear after stage is completed. Maybe it is better to use sorted array/vector then, but it is another question.

Nox · Post by **Nox** » Thu Dec 03, 2009 9:35 pm

I guess you tested this with release mode exe and started it without the ide. Moreover you disabled _SECURE_SCL too, right?

torleif · Post by **torleif** » Thu Dec 03, 2009 11:21 pm

It's my understanding that std::map is actually a red-black tree, so it will be slightly slower than irrmap. I assume irrmap is an actual hash map.

Kojack · Post by **Kojack** » Fri Dec 04, 2009 5:31 am

It's not a hash map. From the top of irrmap.h:

Code: Select all

//! map template for associative arrays using a red-black tree

zet.dp.ua · Post by **zet.dp.ua** » Fri Dec 04, 2009 8:04 am

Nox wrote:I guess you tested this with release mode exe and started it without the ide. Moreover you disabled _SECURE_SCL too, right?

Release, without ide, BUT with _SECURE_SCL 1 (#define _SECURE_SCL 0 affects only iterators and then std iterates faster by ~10%, all other operations have the same relations)

zet.dp.ua · Post by **zet.dp.ua** » Fri Dec 04, 2009 1:23 pm

Tests updated: added stx::btree_map + _SECURE_SCL 0.
Just for information.
Project is here: http://www.multiupload.com/WZV111ONN9

Code: Select all

- Clear, insert, delete

Elements: 100
STL map         time: 1028378
btree_map       time: 484523
irrMap          time: 634296

Elements: 1000
STL map         time: 14384682
btree_map       time: 7098728
irrMap          time: 14063101

Elements: 10000
STL map         time: 191573772
btree_map       time: 94923517
irrMap          time: 1903499715

Elements: 100000
STL map         time: 3181831458
btree_map       time: 1347145085
irrMap          time: 286841801922


- Clear, insert

Elements: 100
STL map         time: 704938
btree_map       time: 260728
irrMap          time: 535886

Elements: 1000
STL map         time: 9534226
btree_map       time: 3633136
irrMap          time: 8790639

Elements: 10000
STL map         time: 123018844
btree_map       time: 48679358
irrMap          time: 115787256

Elements: 100000
STL map         time: 2569503378
btree_map       time: 690916161
irrMap          time: 2613763932


- Access []

Elements: 100
STL map         time: 159055
btree_map       time: 249431
irrMap          time: 151632

Elements: 1000
STL map         time: 2057926
btree_map       time: 3404115
irrMap          time: 1782651

Elements: 10000
STL map         time: 37397581
btree_map       time: 45876675
irrMap          time: 34313500

Elements: 100000
STL map         time: 1725235746
btree_map       time: 707077436
irrMap          time: 1054081717


- Iteration

Elements: 100
STL map         time: 19474
btree_map       time: 8788
irrMap          time: 21411

Elements: 1000
STL map         time: 199251
btree_map       time: 72917
irrMap          time: 231296

Elements: 10000
STL map         time: 2242513
btree_map       time: 714636
irrMap          time: 2509442

Elements: 100000
STL map         time: 45072664
btree_map       time: 8281052
irrMap          time: 52867971