Unicode revisited

Unicode, UTF8, UTF16, UTF32, UCS2, locales and code pages are areas that I looked at 15 years ago.  It has been worth a revisit.
As a reminder old computers used 7 bit ASCII character sets, which was sufficient to store the roman alphabet (both upper and lower case), numbers, some control characters and a bit of puncuation.  This left every other language out in the cold.  Most countries then used the 8th bit in the byte to add their locale specific characters, e.g. the £ symbol in the UK.  However these characters meant different things to different countries, these differences then had to be differenciated by the operating system (as "Code Pages") to display them properly.  To avoid this problem Unicode was invented, it contained all the other characters and diacratics that people wanted in a format that was undersood in all countries.
Unicode came in several formats UCS2, UTF8, UTF16, UTF32.
Back then in the mid 90's UCS2 was the standard to go by, being made of a 16bit character set it was considered sufficient to carry all the characters that the world needed, and that back in the early 90's is what 32 bit Windows NT was designed to use, the legacy of which is present in the latest Windows 7.  UCS2 is easy and fast, and the use of memory is directly proportional to the number of characters making coding for it easy. However it is now becoming clear that that is now not sufficient.  UCS2 can only hold upto 65000 different characters, however more are being required all the time and it is not enough, more memory or an overflow is required, this is where the UTF* implementation is now showing its strength.
The UTF standard uses an overflow principal, with UTF8 a character is made of one or more than one bytes.  The last bit in a byte is a flag indicating that the character needs at least another byte to complete that character.  The same goes for the second byte when a third byte is needed, and so on.  UCS16 is the same, but the flag is only used on the last 16th bit, rather than every eigth as in UTF8.  I am sure that UFT32 also has an overflow bit, but currently that is not needed.
My nose wrinkled when I first looked at is as I did not want this extra complexity that UTF8 provides, I considered UCS2 is the way to go for my future development.  UCS2 is easy you know exactly how much memory you need for a given character length, so you do not need to pre calculate the length of a buffer before you use it.  However unless you are converting between 16 bit and multibyte strings or working with fixed length data formats, e.g. flat files or ODBC, this worry is rarely a consideration.  Secondly UTF8 in practice is more efficient with space.  Even if you are Chinese the spaces, numbers and the occational western word that are common in conteporary text use only one byte and in average use less space than the equivelant 16 bit unicode formats.
So what is important about moving from UCS2 to UTF8?  Microsoft does not seem to care, internally it uses UCS2 in its operating systems (an architecture descision made in the 90's), so it must not care about this difference?  The problem for Microsoft is all its systems cannot be easily changed from UCS2 to UTF16 or some other encoding standard as the change will be traumatic, and costly, so they are choosing to not to make a big deal of it.  The issue is though the web extensively uses UTF8, and with the arrival of new operating systems e.g. Android that directly use it, Microsoft will increasingly look out of step.  This is especially the case in China where only a subset of the chinese character set is available in UCS2.
If you are writing portable internationalised applications then UCS2 is probably not the way to go forward.
Links:
http://site.icu-project.org/
http://utfcpp.sourceforge.net/

FL1 Group workshops

I have been attending a series of free workshops from FL1 Group, although I know a lot about programming I had not appreciated how little I knew about how to make your web presence work properly for you.  Highly recommended, free and Jason makes a nice cup of tea!

What's better than std::map and std::set?

This is a rather dry subject, but I think essential when you think that exabytes of data around the world is held in these structures.  If enough people read this then I think that I would have contributed considerably to reducing global CO2 emissions!  I hope that you will find this a useful launch pad for giving an extra boost to your solution.
Are there faster alternatives and less memory hungry alternatives that we could use as a drop in replacement to std::map and std::set?
The things that I commonly use std::map and std::set for are:

• Allow me to store objects in a retrievable collection.
• Confirm that an object exists in the collection.
• Retrieve objects by entering the key to the data.
• Iterate through the structure in the order specified by the less function (that you can optionally provide).
• Merge collections.
• Get a count of objects in the collections.
• Store objects by value or by pointer.
• and others...

The probem is that these collection classes use memory themselves, aside from the value, each record need memory equal to the size of the key + size of two other pointers to two other adjacent records.
Secondly these two stl classes are slow than some other solutions when searching for data in a large collection especially for strings.
What are the alternatives?  Well there are lots but they basically come down to a short list that do:

Red/black or b-tree

What stl:map/set is made of, traditionally the most flexible, but performance gets hurt when data gets big.  Some of these structures also have problems with node balancing that can have a serious performance hit especially when data is entered already sorted.  Its strong point is that they are very fast in iteration, as the key does not need to be unpacked along with the value.

Hash tables

Fast lookup, but you cannot iterate through nearby key values.  Has performance hits when you have chosen a poor hash algoritum for your data, or the hash table needs to be resized, often this can be fixed by predeclaring how big the table is likely to be.  You cannot iterate through similar values though so is not very useful in similar word searches etc.  The structure of the hash table can also be inefficent with memory as the table may be poorly tuned to the requirements of the data.
If you want the definitive rundown on hashed collection classes have a look at the tommyds site.

Patricia, Ternary and Ned tries, DWAG

Yes tries not trees!  The key (e.g. a string) is split into an array of numbers or charaters and values are found by following a breadcrumb trail of these characters in the memory structure.

Judy array

A highly compact exotic datastructure, that I do not fully understand (maybe one day), it took the bloke years to get it right, and named it after his sister.  I have written an STL style wrapper around it, along with iterators.  The keys are sorted.
Performance Test
Test harness
Below are the results of my tests, I do think that some of my timing results are suspect, and there is a bit of apple and pear comparisons going here however you are welcome to compile my tests and see for your self.  This was done on a lenovo x200 laptop with 64 bit windows 7, core 2 duo, 8 gig of ram running as a 32 bit process.   The collections were made to store 1,000,000 strings containing values "0" to "999,999".
I have tested against
A set of 32 bit values

• std::set<const_char*>
• xt::judy_set<const_char*>

A set of strings

• std::set<std::string>
• xt::judy_string_set

A string map to 32 bit integers

• nPatriciaTrie
• std::map<std::string,int>
• stdext::hash_map<std::string,int>
• ToolBox::Trie
• uxn::patl::trie_map<std::string,int>
• xt::judy_string_map<int>
• xt::judy_string_val_map<int>

The variance of the amount of memory used is considerable, xt::judy_set<const_char*> used 1/10 th of the memory of std::set<const_char*>.  If memory is an issue then Judy is the way to go, it can be much faster if you start paging memory to disk.
Anything that required the contents of the key got a speed penalty.  If your string class did internal reference counting then this helped considerably with the std:: maps and sets, as the key was not copied.
Iteration was the red/black btree main strength, as the key was uncompressed.  This was especially the case when the key value was a std::string, as the other collections had to make them from scratch.
There is only one good reasonably fast all rounder that can do exciting things such as hamming and levenshtein distances is the PATRICIA C++ library.  You can also have a look at the Ternary Search Tree but performance seemed and issue.

Name	clear	copy	find	iterate	load	Memory used
nPatriciaTrie			421		1466	45596
std::map<std::string,int>	375	749	3416	63	5335	55136
std::set<const_char*>	468	531	562	62	1092	31408
std::set<std::string>	405	749	3573	250	4868	54368
stdext::hash_map<std::string,int>	483	1295	1466	32	2418	48480
tommy_hash_tester<char*,int>			31		890	39536
ToolBox::Trie			983		1060	21684
uxn::patl::trie_map<std::string,int>	390	1778	1591	172	2558	54904
xt::judy_set<const_char*>	47	951	499	484	577	3396
xt::judy_string_map<int>	655	0	2168	1950	2683	10248
xt::judy_string_set	671	2902	2044	2059	2714	12500
xt::judy_string_val_map<int>	2184	3058	1997	1950	2762	26212

Links 

Patricia Trie Template Class

nPatriciaTrie is fast but is not a drop in replacement to stl.  Cannot iterate through collections.

Wikipedia Trie

ToolBox::Trie reasonably fast but is not a drop in replacement to stl.  Cannot iterate through collections.

Practical Algorithm Template Library - C++ library on PATRICIA trie

uxn::patl::trie_map<std::string,int>, the true swiss army knife of a map collections, is reasonably fast (and perhaps could go faster with different allocators).  The only one worth looking at for things like hamming and levenshtein distances.

A wrapper to this judy array code

xt::judy_set<const_char*> Judy is not the fastest, but easily the most efficient with memory.

Roguewave sourcepro 9

RWTPtrHashMap<std::string,int,silly_hash,std::equal_to<std::string> > was not a true alternative to stl::map as the interface was too different.  It also did not run too fast with 1000000 records in it.  Perhaps there is a tweek to make it faster, but why pay for something when you can get it for free?

tommy_hash_collection

Very fast, does not work with string keys, which is my main interest.  Their web site contains some excellant benchmarking data, probably far more accurate then mine!  A good source if you are interested in some in depth info on hashed indexes.

jdktrie

I had problems with this one and had to hack a few lines to make it run, I will look at this another time.

Ternary Search Tree 

[containers::structured_set Probably as] powerful as uxn::patl::trie_map but on my machine it was very slow.

pb_ds trie

Would not compile as there is too much dependency on the GCC libraries that would have required me to rewrite my test harness.  Has an bsd style licence but dependent on GPL code, not sure if I could use this in commercial software.

Ned Tries

Currently not tested

google-sparsehash

Currently not tested

boost::spirit

There is a trie implementation in there somewhere, not tested.

DAWG

Directed acyclic word graph