This is a repost of an earlier response to another thread. I did not recieve any response so I am posting this in its own thread.

I have several old books (circa 1991), including source code, covering TP6 in my library.
Perhaps the most interesting one covers generic programming. It covers modelling generic data stuctures including:
Generic Stacks
Generic Queques
Generic Arrays
Generic Virtual Arrays
Generic Matrices
Generic Jagged Matrices
Generic Internal Hash Tables
Generic Singly Linked Lists
Generic Doubly Linked Lists
Generic AVL Trees
Generic Graphs

If any of these are of interest, please respond because I will have to rework the code for it to compile cleanly using FPC.

Regards

John

Dean Zobec is working on Decal, which contains a classes-based implementation of this kind of objects.

Michael.

I still remember the Algorithms + Data Structures = Programming book from Niklaus Wirth back in 1976, it was a masterpiece. I'll try to find it in a library to reread it :-)

As you've probably heard from Florian, FPC needs a good containers library. I've started looking at Decal this week, the code has been ported to fpc by Marco Van de Voort and now compiles with FPC. It's based on the TVarRec and open array construction (array of const) to be able to add to the containers even the base types as integers, floats, chars, etc.
The generic functions are very powerful and model closely the C++ STL library (as fpc does not have generics yet a sort of typecast is still required when fetching the items from the container). The library was not designed for speed though, from the first test the DArray class is twice as slow then the TFPList for example). Anyway, I think it's a good start, since as I've seen from the wiki, we'll not have generics in fpc available soon (I would be glad to contribute to the generics implementation, but this but is still beyond my current poor fpc knowledge :( ) . When our compiler will support generics, if Decal will be fully covered by unit tests I think it will be easier to convert to it.

The code is available in the old fpc cvs under the directory projects/contrib/decal. I've began to clean the unit to make it more readable, moving the comments in a fpdoc xml file and restoring a proper indentation.
Then I'm planning to pin down the code with unit tests with FPCUnit to begin a refactoring in case there are potential speed improvements and to remove possible bugs (I've seen a lot of strange comments in the code that does not smell very good). The unit is quite big, more or less 9.000 lines of code, and quite complicated, so I'll surely need help. In any case I'm very interested on the subject of container classes so I'm glad to discuss it with other people interested in it.

As the project looks like a long term one and I think that fpc urgently needs a optimized hash table I'll also work on a streamlined hash table with a chaining technique as a collision resolution scheme and a paging for the allocation of the nodes in the chains, to have an associative container that would easily beat the TStringList in search speed when the number of items added is more than 100.000 (the IndexOf() function in an unordered TStringList does a linear search).

I would be glad to receive opinions on the container classes implementation in FPC and of course we'll surely need help (I'm not working as a professional programmer, I even do not work in the IT field, so my programming work as an hobby is limited to the evenings), so feel free to get in contact with me even in private if you prefer.

Ciao,
Dean

A good hash class is even a candidate for the classes unit imo.

At work, I have found out that decal is too bulky and too slow for some purposes (I've lists with millions of objects in memory). _each_ entry in a decal container eats 78 byte (with D6 memory manager, but will only be equal or larger with FPC)

For this, I implemented dirty, but very fast maps and sets. These are not generic, but fast, and with FPC they can really fly due to inline capabilities. See

http://www.stack.nl/~marcov/lightcontainers.zip

projects/contrib/decal. I've began to clean the unit to make it more readable, moving the comments in a fpdoc xml file and restoring a proper indentation.

I have a tex version of the decal docs somewhere.

http://www.stack.nl/~marcov/decal.tex (might use some FPC tex docs files)

compiled to

http://www.stack.nl/~marcov/decal.pdf

Something variants based is not though, at least IMHO.

Note that the Technetium people (Flawless and Aison on IRC) have several of such routines. At least all the algo's are there and tested, only class wrapper would be needed.

Depends how the hash is parametrized. If you've a big hash array and a good hash function accessing has a complexity of O(1) while for a binary search it's O(log(n))

I would make that the contnrs unit. I think it belongs more together with objects such as a stack and queue...

What is the performance difference between a hash() and a binary search on an ordered list ? I've also been working with an 'associative' stringlist, but I was using an ordered stringlist to keep the data, so a binary search is done.

Michael.

But I assume that calculating the hash becomes harder for 'better' hashes ?

Michael.

This is no fair comparison, since you compare an unsafe way (hash) with a safe one (bintree).

So this only if you have a number of buckets close to the number of elements and a perfect hash. Otherwise you need log(n1/nbuckets) extra comparisons. (assuming you do conflict resolving using bintree)

Note also that bintree is a bit outdated since most datastructures texts measure datastructures in comparisons. However _if_ some of your comparisons are not equal in speed the spectrum changes.

Compare e.g. a bintree to a quadtree.

type
 pbintree = ^tbintree;
 tbintree = record
		value: array [0..0] of integer; // one int
		ptrs: array[0..1] of pbintree;
			// left right is more traditional but this is clearer
		end;
 pquadtree= ^tquadtree;
 tquadtree = record
		value: array [0..2] of integer; // one int
		ptrs: array[0..3] of pquadtree;
			// left right is more traditional but this is clearer
		end;

The bintree does about log(n) comparisons. So does the quadtree. (it must do more comparisons per record, but the tree depth is about proportionally less). However the per record quadtree comparisons are cached, making it faster AND more memory intensive.

There is also dynamic hashing, where the number of buckets grow/shrink dynamically with addnig items. Then it stays O(1), but the constant involved may be so large that it's practically slower than binary tree, until using a lot of items, a million say (for example).

Micha

Not always, it depends on the type of the input, different hash functions have to be used for different key types, a hash function good for numerical keys will be different from the hash function used for the string keys. My idea is to add to the hash table a method for "statistical" data about the table: number of collisions, i.e. length of the chains and the number of void buckets in the hash array, to be able to choose the right hash function and the right dimension for the hash array in the specific case.
Of course speed comes always at an expense: memory usage, the trick is to find a good compromise.
Ciao, Dean

The TStringList is a very fast class, if you worked with less than 100.000 items you would not notice any difference. But a Hash Table is also very fast in insertion, while to keep a list ordered only for searching may be not convenient and slows down insertion. Ciao, Dean

Only for general purpose hashes. Specific hashes are easier. This is where templates/generics come into play.

You can then instantiate an hash container with a custom hashing code _specific for your current application_ while avoiding any overhead, (and remaining typesafe, but that is not relevant to this discussion)

I can immagine, the DObject is a TVarRec. The problem with speed and memory usage are the things that I don't like in Decal and it still makes me wonder if it would be better to reimplement a containers library from scratch, if we had generics to add type checking at compile time... I'm looking at all the options (time is a limited resource :).

Thank you, I'll take a look in the next few days. Maybe we could build on this instead.

Thank you, I had your pdf but not the tex file.

Ciao, Dean

Generics are indeed very nice to have. But if we want a nice data structures and algorithms package before generics are implemented, we will have to do without for now.

When Generics are supported by the compiler, the unit(s) could be adapted to use Generics. By that time, there would be quite some feedback and experience from the first implementation. This can help creating a package using Generics that is also well designed. (i.e. we can learn from 'mistakes' in the first implementation)

On the other hand, there is already a lot of experience from other similar libraries, such as Decal, STL, java.util, etc. But that might not be part of the experience of the programmer implenting such a package for FPC.

Besides using TVarRecs, we could also use pointers (as in classes.TList) or objects. This would perhaps be a bit like it is in java.util. Then we would also need container classes for basic types such as boolean, integer, string and float. I'm not sure whether this is indeed a good plan, but I'm just mentioning it because you said you want to look at 'all the options' :)

Anyway, I'm very interested in a library with commonly used generic data structures and algorithms, and I think there are many more such developers. So I'd say: keep up the goods plans & work!

Regards,

Bram

I did not mention variants, I do not intend to use them. I'll try to streamline and polish a class I've used in a previous project: See the TDZNotOwnerHashTable at the end of the unit: http://cvs.sourceforge.net/viewcvs.py/camelos/EOS/fpcEOS/dzcontain.pp?rev=1.1&view=markup

Thank you, I'll get in contact with them.

Ciao, Dean

Bram Kuijvenhoven wrote

Besides using TVarRecs, we could also use pointers (as in classes.TList) or objects.

Pointers like in TList were the things I had in mind.

Yes, the containers for basic types could be constructed as wrappers, the pointer based containers would be incapsulated.

Good to know that are many people interested in the subject. I'm sure I'll learn a lot of things from them, as always in this great community :) Ciao, Dean

Better finish decal. DeCal is good and comfortable for most cases, and trying to speed it up will kill the ease of use.

Then we can collect some other set of routines over time for more performance dependant stuff.

It's not as friendly ;-)

Thank you, I had your pdf but not the tex file.

If we move decal to packages/contrib, we can move the docs to the fpcdocs dir ?

Michael Van Canneyt wrote

What is the performance difference between a hash() and a binary search on an ordered list ?

IMO perfomance heavily depends on the use of the lists. An ordered list requires some efforts when entering or removing items, and typically requires more comparisons than a hashed list. Access to a hashed list, with a reasonable hash table size, requires not much more than one comparison, whereas an ordered list requires log(n) comparisons.

A hash algorithm can be very simple, in detail for generic hash tables with no constraints on the distribution of the element keys. For collission handling I prefer a linked list of the affected elements, over re-hashing.

I've also been working with an 'associative' stringlist, but I was using an ordered stringlist to keep the data, so a binary search is done.

When the list elements are stored by reference, it's possible to maintain any number of related tables (indices, hash tables). When a sorted list is already required for the elements, an (additional) hash table is optional.

As long as the same list interface is implemented for all access models, it's quite easy to exchange the implementation in order to find out the best performant model for every specific case. The comparison functions should already be exchangeable, according to the nature of the key fields, and the hash algorithms must be exchangeable for the same reason. In so far I wouldn't restrict a library to one specific implementation model for every container type.

In my parser symbol table I add all symbols in creation order to the table, and maintain a hash table for quick access. The hash table grows together with the number of elements, what requires a reorganization of the hash table whenever the symbol list is extended, so that a reasonable starting capacity and increment should be choosen; I double the capacity on every extension. Elements of the same name, but in different scopes, are entered into the collission list of the hash table, again in creation order. This simplifies access to the newest symbols, in the current scope, and also simplifies the removal of a complete scope from the symbol and hash tables. Please note that duplicate keys require special efforts in sorted lists, when the creation order of the elements, or any other secondary sorting criterium, is significant.

DoDi

I am reading this manual now, because I want to familiarize myself with this lib. Meanwhile I am finding some typo's, so I am fixing the tex file (I will send a patch when done).

The fpc.sty and fakehtml.sty files required are on http://svn.freepascal.org/svn/fpcdocs/trunk/, but I need pics/decalhier.eps if I want to compile the tex file. Where can I find it?

Regards,

Bram

I found a png, but can't seem to find the original file (it is in .dia format), will have to search for it.

http://www.stack.nl/~marcov/decalhier.png

You are right, it will be probably the easier way.

Ouch, it bites, ehmmm.... or should I say it bytes ;) Very interesting stuff, but not for mere mortals like me :)
Really out of my reach. I'll try to play with it, just to try to see how it works (even if I doubt I'll be able to understand the compiler god's code :)

Ciao, Dean

Mere RTL god ;)

Marco van de Voort wrote

I found a png, but can't seem to find the original file (it is in .dia format), will have to search for it. http://www.stack.nl/~marcov/decalhier.png

If you can't find the eps - or never had any - I can create one on my own (using xfig).

Anyway, here is a patch for the tex file which fixes
- unwanted extra } at the end of code line
- some small errors in the text
- unwanted spaces in \emph and \textbf
- removed tabs in code
- fixed new paragraphs starting in the middle of a sentence Still remaining problems are:
- the lstlisting environment doesn't highlight Pascal properly
- some lines of code are too long
and I probably have overlooked some remaning errors of course.

Perhaps the lstlisting should be replaced by some command from fpc.sty?

The use of TVarRec has it's disadvantages when it comes to speed and memory usage, but definitely makes things easier for the programmer. I think only Generics can beat that! I don't know whether the internals of Decal are bulky, but that doesn't result simply from using TVarRec.

Btw TVarRec is only 8 bytes in size, where variants require 16, so it isn't /that/ bad :)

Anyway, for high perfomance it is better to store only a pointer. In that case the programmer has to inform the container about the type it actually stores (or pass a custom comparator) so the container knows how to compare items.

Besides containers, there is also the SuperStream library, which seems to be very nice too. For this library, the use of TVarRec makes life easier too. Though maybe using RTTI and published properties can be easier, the scheme of SuperStream is very powerful.

Note for people searching for .pas sources: the original sources from Soletta are on http://cvs.sourceforge.net/viewcvs.py/decal/ and are also (modified) on fpc cvs/contrib (http://www.freepascal.org/cgi-bin/viewcvs.cgi/contrib/decal/?root=projects).

Regards,

Bram