Re: [fpc-devel] Generic Programming Units
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 :) Mere RTL god ;) ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Generic Programming Units
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
304c304,306
Guide section of this manual fairly
---
Guide
section of this manual fairly
376,378c378
\item As an archive, downloaded from the internet. The original sources from
Soletta are on the following CVS repository on SourceForge:
\url{http://cvs.sourceforge.net/viewcvs.py/decal/}
---
\item As an archive, downloaded from the internet
737c737
For I := 0 to list.count - 1 do
---
For I := 0 to list.count -- 1 do
742c742
For I := 0 to list.count - 1 do
---
For I := 0 to list.count -- 1 do
826c826
Function GenMix(ptr : Pointer) : DObject;
---
Procedure GenMix;
839c839
case obj.vtype of
---
case obj.vtype of}
932c932
the objects (it is a \emph{shallow} copy of the arr container).
---
the objects (it is a \`{\i}shallow\^{\i} copy of a the arr container).
1062c1062
\section{Lesson 5 -- Using Maps (Key-Value Pairs)}
---
\section{Lesson 5 -- Using Maps (Key-Value Pairs}
1163c1163
Writeln(`Found Ted Jones, whose id is `, emp.id);
---
Writeln(`Found Ted Jones, whose id is `, emp.id;
1202c1202
For I := 1 to 50 do
---
For I := 1 to 50 do}
1280c1280
Result := CompareText(TEmployee( getObject(obj1)).name, TEmployee(
getObject(obj2)).name);
---
Result := CompareText(TEmployee( getObject(obj1)).name, TEmployee(
getObject(obj2)).name));
1348c1348
For I := 1 to 10 do
---
For I := 1 to 10 do}
1402c1402
Since we really want remove to run fast, we change our data structure
---
Since we really want that remove to run fast, we change our data structure
1481c1481
Result := TEmployee(getObject(obj)).salary = 5;
---
Result := TEmployee(getObject(obj)).salary $$= 5;
1487c1487
Result := CompareText(TEmployee( getObject(obj1)).name, TEmployee(
getObject(obj2)).name);
---
Result := CompareText(TEmployee( getObject(obj1)).name, TEmployee(
getObject(obj2)).name));
1639c1639
Figure 1 shows the SDL container class hierarchy.
---
Figure 1 shows the SDL container class hierarchy:
1734c1734,1736
When you retrieve an iterator from one of these containers, the iterator will
---
When
you retrieve an iterator from one of these containers, the iterator will
1877,1878c1879,1880
\textbf{zero} if obj1 equals obj2, and
\textbf{greater than zero} if obj1 is greater than obj2.
---
\textbf{zero} if obj2 equals obj2, and
\textbf{greater than zero} if obj2 is greater than obj1.
1885c1887
ACar := asObject(obj1) as TCar
---
ACar := asObject(obj1) as TCar}
1893c1895
Result := TCar(obj1.VObject).FValue - TCar(obj2.VObject).FValue;
---
Result := TCar(obj2.VObject)^.FValue - TCar(obj1.VObject)^.FValue;
2044c2046
PushFront(item)
---
PushFront(item)}
2059c2061
PopBack
---
PopBack}
2138,2139c2140,2141
use the correct form with assertions. Note that it doesn't make any sense to
try to add elements directly to a map (because you haven't supplied the
---
use the correct form with assertions. Note that is doesn't make any sense to
try to add elements directly to a map (because you haven't) supplied the
2141c2143
to a set (because there isn't any
Re: [fpc-devel] Generic Programming Units
Marco van de Voort wrote: 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 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 ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Generic Programming Units
Marco van de Voort wrote: 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 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? 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 ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Generic Programming Units
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 ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Generic Programming Units
Marco van de Voort wrote: 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. You are right, it will be probably the easier way. 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 Thank you, I'll take a look in the next few days. Maybe we could build on this instead. It's not as friendly ;-) 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 ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Generic Programming Units
On Tue, 21 Jun 2005, John Briggs wrote: 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. Dean Zobec is working on Decal, which contains a classes-based implementation of this kind of objects. Michael. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Generic Programming Units
John Briggs wrote: 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. 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 :-) 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 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 ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Generic Programming Units
Dean Zobec wrote: 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). A good hash class is even a candidate for the classes unit imo. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Generic Programming Units
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. 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 ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Generic Programming Units
Dean Zobec wrote: 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). A good hash class is even a candidate for the classes unit imo. 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. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Generic Programming Units
On Tue, 21 Jun 2005, Florian Klaempfl wrote: Dean Zobec wrote: 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). A good hash class is even a candidate for the classes unit imo. 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. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Generic Programming Units
Michael Van Canneyt wrote: On Tue, 21 Jun 2005, Florian Klaempfl wrote: Dean Zobec wrote: 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). A good hash class is even a candidate for the classes unit imo. 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. 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)) ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Generic Programming Units
On Tue, 21 Jun 2005, Florian Klaempfl wrote: Michael Van Canneyt wrote: On Tue, 21 Jun 2005, Florian Klaempfl wrote: Dean Zobec wrote: 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). A good hash class is even a candidate for the classes unit imo. 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. 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)) But I assume that calculating the hash becomes harder for 'better' hashes ? Michael. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Generic Programming Units
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. 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)) 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. ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Generic Programming Units
Michael Van Canneyt wrote: 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)) But I assume that calculating the hash becomes harder for 'better' hashes ? 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 ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Generic Programming Units
Michael Van Canneyt wrote: 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. 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 ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Generic Programming Units
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)) But I assume that calculating the hash becomes harder for 'better' hashes ? 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) ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Generic Programming Units
Marco van de Voort wrote: 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. 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) 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 :). 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 Thank you, I'll take a look in the next few days. Maybe we could build on this instead. 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) Thank you, I had your pdf but not the tex file. Ciao, Dean ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Generic Programming Units
Dean Zobec wrote: 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 :). 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 ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Generic Programming Units
Marco van de Voort wrote: Dean Zobec wrote: 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). A good hash class is even a candidate for the classes unit imo. Something variants based is not though, at least IMHO. 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.1view=markup 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. Thank you, I'll get in contact with them. Ciao, Dean ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
Re: [fpc-devel] Generic Programming Units
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. 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' :) Yes, the containers for basic types could be constructed as wrappers, the pointer based containers would be incapsulated. 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! 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 ___ fpc-devel maillist - fpc-devel@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-devel
