Sign in Join

Live chat for Free Pascal, Lazarus, Delphi and every Pascal programmer.

Mailing lists / fpc-pascal / 2010-10

IntList

14 messages · 9 people · –

Reply by email Subscribe to this list Your subscription

Read-only archive. Use j and k to move between messages.

Juha Manninen (gmail

Hi

In Lazarus project jcf2 component has an IntList class which is poorly implemented. It depends on integer and pointer being the same size. I will later suggest to replace it.

I have a better IntList. See:
http://github.com/JuhaManninen/Pascal/blob/master/IntList/intlist.pas

It is similar to TStringList except that it works with integers. It is well tested.

Question: can this class be added to FCL?
Clearly such class is needed sometimes and people must make their own versions of it. Generics can solve it in the future but it is not ready yet.

If it can't be included then I try to get it to Lazarus libraries.

Regards,
Juha

Luiz Americo Pereira Camara
to Juha Manninen (gmail
Juha Manninen wrote 16 lines
Hi In Lazarus project jcf2 component has an IntList class which is poorly implemented. It depends on integer and pointer being the same size. I will later suggest to replace it. I have a better IntList. See: http://github.com/JuhaManninen/Pascal/blob/master/IntList/intlist.pas It is similar to TStringList except that it works with integers. It is well tested. Question: can this class be added to FCL? Clearly such class is needed sometimes and people must make their own versions of it. Generics can solve it in the future but it is not ready yet.

Yes it's ready in fpc 240:

uses
  Fgl;
type
  TIntegerList = specialize TFPGList <Integer>;

Luiz

Juha Manninen (gmail
to Luiz Americo Pereira Camara
Luiz Americo Pereira Camara wrote 7 lines
Yes it's ready in fpc 240: uses Fgl; type TIntegerList = specialize TFPGList <Integer>;

Well, yes. It is almost as good as a dedicated class. It has a Sort method but you must feed the compare function for it.
It does not have a Find method for a binary search in a sorted list. Indexof does a linear search.

Anyway, it could be used as a base class in Lazarus. I don't know what is the Lazarus team's policy for using generics in Lazarus code-base.

In FPC 2.4.0 I had problems with memory consumption of generics containers. A <Integer, Integer> map hogged gigabytes of memory while my data took only kilobytes (less than 1 MB for sure), on a 64 bit Linux. Now I have the latest FPC trunk 2.5.1 and the problems are gone. I added 100000 integers to both a List and to a Map and didn't even notice the memory increase in resource monitor.

  TIntegerList = specialize TFPGList <Integer>;
  TIntegerMap = specialize TFPGMap <Integer, Integer>;

TFPGMap's problem still is that it is not a hash map and is butt-slow with lots of data. A hash map is a superior container type, it really should be changed.
Besides, people expect to get a hash map when they see "map" in the class name. Now they get a list which is deceivingly named as "map".

Juha

Sven Barth
to Juha Manninen (gmail
Juha Manninen (gmail) wrote 32 lines
On Tuesday 19 October 2010 19:10:39 Luiz Americo Pereira Camara wrote: > Yes it's ready in fpc 240: > > uses > Fgl; > > type > TIntegerList = specialize TFPGList<Integer>; Well, yes. It is almost as good as a dedicated class. It has a Sort method but you must feed the compare function for it. It does not have a Find method for a binary search in a sorted list. Indexof does a linear search. Anyway, it could be used as a base class in Lazarus. I don't know what is the Lazarus team's policy for using generics in Lazarus code-base. In FPC 2.4.0 I had problems with memory consumption of generics containers. A<Integer, Integer> map hogged gigabytes of memory while my data took only kilobytes (less than 1 MB for sure), on a 64 bit Linux. Now I have the latest FPC trunk 2.5.1 and the problems are gone. I added 100000 integers to both a List and to a Map and didn't even notice the memory increase in resource monitor. TIntegerList = specialize TFPGList<Integer>; TIntegerMap = specialize TFPGMap<Integer, Integer>; TFPGMap's problem still is that it is not a hash map and is butt-slow with lots of data. A hash map is a superior container type, it really should be changed. Besides, people expect to get a hash map when they see "map" in the class name. Now they get a list which is deceivingly named as "map".

As you seem to have experience with efficient data structures, what about creating such a generic hash map? :)

(but don't use 2.4.2rc1 and current/unpatched 2.4.3 as a test base as those don't have the fixes from trunk to make "specialize" working again)

Regards,
Sven

Michael Van Canneyt
to Sven Barth
Sven Barth wrote 42 lines
Am 19.10.2010 19:54, schrieb Juha Manninen (gmail): > On Tuesday 19 October 2010 19:10:39 Luiz Americo Pereira Camara wrote: >> Yes it's ready in fpc 240: >> >> uses >> Fgl; >> >> type >> TIntegerList = specialize TFPGList<Integer>; > > Well, yes. It is almost as good as a dedicated class. It has a Sort method > but > you must feed the compare function for it. > It does not have a Find method for a binary search in a sorted list. > Indexof does a linear search. > > Anyway, it could be used as a base class in Lazarus. I don't know what is > the > Lazarus team's policy for using generics in Lazarus code-base. > > In FPC 2.4.0 I had problems with memory consumption of generics containers. > A<Integer, Integer> map hogged gigabytes of memory while my data took only > kilobytes (less than 1 MB for sure), on a 64 bit Linux. > Now I have the latest FPC trunk 2.5.1 and the problems are gone. I added > 100000 integers to both a List and to a Map and didn't even notice the > memory > increase in resource monitor. > > TIntegerList = specialize TFPGList<Integer>; > TIntegerMap = specialize TFPGMap<Integer, Integer>; > > TFPGMap's problem still is that it is not a hash map and is butt-slow with > lots of data. A hash map is a superior container type, it really should be > changed. > Besides, people expect to get a hash map when they see "map" in the class > name. Now they get a list which is deceivingly named as "map". As you seem to have experience with efficient data structures, what about creating such a generic hash map? :) (but don't use 2.4.2rc1 and current/unpatched 2.4.3 as a test base as those don't have the fixes from trunk to make "specialize" working again)

Currently, the FPC team is looking at an implementation of Vlado Boza for a standard template library for inclusion in FPC.

The code is on

http://code.google.com/p/stlpascal

Please have a look and comment on it.

I'm not a generics expert and am not in the position to judge whether this library is good or not.

Michael.

Brian Winfrey
to Michael Van Canneyt

Take a look at http://code.google.com/p/fprb/. I have just perused it, but it looks pretty good.

Brian.

Show quoted text 18 lines
Currently, the FPC team is looking at an implementation of Vlado Boza for a standard template library for inclusion in FPC. The code is on http://code.google.com/p/stlpascal Please have a look and comment on it. I'm not a generics expert and am not in the position to judge whether this library is good or not. Michael. _______________________________________________ fpc-pascal maillist  -   http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Honza
to Brian Winfrey

2010/10/19 Brian Winfrey :

Take a look at http://code.google.com/p/fprb/.  I have just perused it, but it looks pretty good.

I'm willing to cooperate (as free time permits) on any required FPRB/heLib review/modification process would any part(s) of the code be considered/adopted by the dev team, including but not limited to (re)releasing the code under a FCL compatible license (currently New BSD). Just let me know if/what is necessary.

bflm freepascal-bits.blogspot.com
Vlado Boza
to Michael Van Canneyt: Currently, the FPC team is looking at an implementation of Vlado Boza for a standard…
Michael Van Canneyt wrote 68 lines
On Tue, 19 Oct 2010, Sven Barth wrote: > Am 19.10.2010 19:54, schrieb Juha Manninen (gmail): >> On Tuesday 19 October 2010 19:10:39 Luiz Americo Pereira Camara wrote: >>> Yes it's ready in fpc 240: >>> >>> uses >>> Fgl; >>> >>> type >>> TIntegerList = specialize TFPGList<Integer>; >> >> Well, yes. It is almost as good as a dedicated class. It has a Sort >> method but >> you must feed the compare function for it. >> It does not have a Find method for a binary search in a sorted list. >> Indexof does a linear search. >> >> Anyway, it could be used as a base class in Lazarus. I don't know >> what is the >> Lazarus team's policy for using generics in Lazarus code-base. >> >> In FPC 2.4.0 I had problems with memory consumption of generics >> containers. >> A<Integer, Integer> map hogged gigabytes of memory while my data >> took only >> kilobytes (less than 1 MB for sure), on a 64 bit Linux. >> Now I have the latest FPC trunk 2.5.1 and the problems are gone. I >> added >> 100000 integers to both a List and to a Map and didn't even notice >> the memory >> increase in resource monitor. >> >> TIntegerList = specialize TFPGList<Integer>; >> TIntegerMap = specialize TFPGMap<Integer, Integer>; >> >> TFPGMap's problem still is that it is not a hash map and is >> butt-slow with >> lots of data. A hash map is a superior container type, it really >> should be >> changed. >> Besides, people expect to get a hash map when they see "map" in the >> class >> name. Now they get a list which is deceivingly named as "map". > > As you seem to have experience with efficient data structures, what > about creating such a generic hash map? :) > > (but don't use 2.4.2rc1 and current/unpatched 2.4.3 as a test base as > those don't have the fixes from trunk to make "specialize" working > again) Currently, the FPC team is looking at an implementation of Vlado Boza for a standard template library for inclusion in FPC. The code is on http://code.google.com/p/stlpascal Please have a look and comment on it. I'm not a generics expert and am not in the position to judge whether this library is good or not. Michael.

Hash_map implementation shouldn't be a big problem. But I also think, that other structures can be usefull as well (for example in map done by red-black tree you can find greatest key which less than X in a good time, ...).

A is there any decision if it is worth to put it in FPC and where to put it?

Vlad.

Michael Van Canneyt
to Vlado Boza
Vlado Boza wrote
On 10/19/2010 08:28 PM, Michael Van Canneyt wrote:

[snip]

Show quoted text 18 lines
> > The code is on > > http://code.google.com/p/stlpascal > > Please have a look and comment on it. > > I'm not a generics expert and am not in the position to judge whether this > library is good or not. > > Michael. > Hash_map implementation shouldn't be a big problem. But I also think, that other structures can be usefull as well (for example in map done by red-black tree you can find greatest key which less than X in a good time, ...). A is there any decision if it is worth to put it in FPC and where to put it?

There is no decision yet. I will ask again and get back to you.

Michael.

Michael Van Canneyt
to Vlado Boza: Hash_map implementation shouldn't be a big problem. But I also think, that other…

Hi,

I asked around.

We'd like to propose the following:
- We import the code in the FPC subversion repository, in a package.
- You get read/write access to the package, so you can maintain it. Subject to 2 conditions:

- You use the FPC license.
- Please remove all _ characters at the start of identifiers. This goes against our coding rules.
(we try to avoid _ as much as possible)

If you can agree with this, I'll import the code in the FPC repository.

Michael.

Vlado Boza wrote 78 lines
On 10/19/2010 08:28 PM, Michael Van Canneyt wrote: > > > On Tue, 19 Oct 2010, Sven Barth wrote: > >> Am 19.10.2010 19:54, schrieb Juha Manninen (gmail): >>> On Tuesday 19 October 2010 19:10:39 Luiz Americo Pereira Camara wrote: >>>> Yes it's ready in fpc 240: >>>> >>>> uses >>>> Fgl; >>>> >>>> type >>>> TIntegerList = specialize TFPGList<Integer>; >>> >>> Well, yes. It is almost as good as a dedicated class. It has a Sort >>> method but >>> you must feed the compare function for it. >>> It does not have a Find method for a binary search in a sorted list. >>> Indexof does a linear search. >>> >>> Anyway, it could be used as a base class in Lazarus. I don't know what is >>> the >>> Lazarus team's policy for using generics in Lazarus code-base. >>> >>> In FPC 2.4.0 I had problems with memory consumption of generics >>> containers. >>> A<Integer, Integer> map hogged gigabytes of memory while my data took >>> only >>> kilobytes (less than 1 MB for sure), on a 64 bit Linux. >>> Now I have the latest FPC trunk 2.5.1 and the problems are gone. I added >>> 100000 integers to both a List and to a Map and didn't even notice the >>> memory >>> increase in resource monitor. >>> >>> TIntegerList = specialize TFPGList<Integer>; >>> TIntegerMap = specialize TFPGMap<Integer, Integer>; >>> >>> TFPGMap's problem still is that it is not a hash map and is butt-slow >>> with >>> lots of data. A hash map is a superior container type, it really should >>> be >>> changed. >>> Besides, people expect to get a hash map when they see "map" in the class >>> name. Now they get a list which is deceivingly named as "map". >> >> As you seem to have experience with efficient data structures, what about >> creating such a generic hash map? :) >> >> (but don't use 2.4.2rc1 and current/unpatched 2.4.3 as a test base as >> those don't have the fixes from trunk to make "specialize" working again) > > Currently, the FPC team is looking at an implementation of Vlado Boza > for a standard template library for inclusion in FPC. > > The code is on > > http://code.google.com/p/stlpascal > > Please have a look and comment on it. > > I'm not a generics expert and am not in the position to judge whether this > library is good or not. > > Michael. > Hash_map implementation shouldn't be a big problem. But I also think, that other structures can be usefull as well (for example in map done by red-black tree you can find greatest key which less than X in a good time, ...). A is there any decision if it is worth to put it in FPC and where to put it? Vlad. _______________________________________________ fpc-pascal maillist - http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Michael Van Canneyt
to Michael Van Canneyt

Sorry,

This was meant to be a private message.

For those interested: the idea is to have a standard set of generics definitions that implement some commonly-used templates. A kind of STL in pascal.

Michael.

Michael Van Canneyt wrote 107 lines
Hi, I asked around. We'd like to propose the following: - We import the code in the FPC subversion repository, in a package. - You get read/write access to the package, so you can maintain it. Subject to 2 conditions: - You use the FPC license. - Please remove all _ characters at the start of identifiers. This goes against our coding rules. (we try to avoid _ as much as possible) If you can agree with this, I'll import the code in the FPC repository. Michael. On Wed, 3 Nov 2010, Vlado Boza wrote: > On 10/19/2010 08:28 PM, Michael Van Canneyt wrote: >> >> >> On Tue, 19 Oct 2010, Sven Barth wrote: >> >>> Am 19.10.2010 19:54, schrieb Juha Manninen (gmail): >>>> On Tuesday 19 October 2010 19:10:39 Luiz Americo Pereira Camara wrote: >>>>> Yes it's ready in fpc 240: >>>>> >>>>> uses >>>>> Fgl; >>>>> >>>>> type >>>>> TIntegerList = specialize TFPGList<Integer>; >>>> >>>> Well, yes. It is almost as good as a dedicated class. It has a Sort >>>> method but >>>> you must feed the compare function for it. >>>> It does not have a Find method for a binary search in a sorted list. >>>> Indexof does a linear search. >>>> >>>> Anyway, it could be used as a base class in Lazarus. I don't know what >>>> is the >>>> Lazarus team's policy for using generics in Lazarus code-base. >>>> >>>> In FPC 2.4.0 I had problems with memory consumption of generics >>>> containers. >>>> A<Integer, Integer> map hogged gigabytes of memory while my data took >>>> only >>>> kilobytes (less than 1 MB for sure), on a 64 bit Linux. >>>> Now I have the latest FPC trunk 2.5.1 and the problems are gone. I added >>>> 100000 integers to both a List and to a Map and didn't even notice the >>>> memory >>>> increase in resource monitor. >>>> >>>> TIntegerList = specialize TFPGList<Integer>; >>>> TIntegerMap = specialize TFPGMap<Integer, Integer>; >>>> >>>> TFPGMap's problem still is that it is not a hash map and is butt-slow >>>> with >>>> lots of data. A hash map is a superior container type, it really should >>>> be >>>> changed. >>>> Besides, people expect to get a hash map when they see "map" in the >>>> class >>>> name. Now they get a list which is deceivingly named as "map". >>> >>> As you seem to have experience with efficient data structures, what about >>> creating such a generic hash map? :) >>> >>> (but don't use 2.4.2rc1 and current/unpatched 2.4.3 as a test base as >>> those don't have the fixes from trunk to make "specialize" working again) >> >> Currently, the FPC team is looking at an implementation of Vlado Boza >> for a standard template library for inclusion in FPC. >> >> The code is on >> >> http://code.google.com/p/stlpascal >> >> Please have a look and comment on it. >> >> I'm not a generics expert and am not in the position to judge whether this >> library is good or not. >> >> Michael. >> > > Hash_map implementation shouldn't be a big problem. But I also think, that > other structures can be usefull as well (for example in map done by > red-black tree you can find greatest key which less than X in a good time, > ...). > > A is there any decision if it is worth to put it in FPC and where to put > it? > > Vlad. > _______________________________________________ > fpc-pascal maillist - > http://lists.freepascal.org/mailman/listinfo/fpc-pascal > _______________________________________________ fpc-pascal maillist - http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Florian Klaempfl
to Michael Van Canneyt
Michael Van Canneyt wrote 8 lines
Sorry, This was meant to be a private message. For those interested: the idea is to have a standard set of generics definitions that implement some commonly-used templates. A kind of STL in pascal.

You are aware of the fgl unit in the rtl? It is supposed to be something like this.

Marco van de Voort
to Florian Klaempfl

In our previous episode, Florian Klaempfl said:

Show quoted text 10 lines
> Sorry, > > This was meant to be a private message. > > For those interested: the idea is to have a standard set of generics > definitions that implement some commonly-used templates. A kind of STL > in pascal. You are aware of the fgl unit in the rtl? It is supposed to be something like this.

The fgl unit seems more targeted at implementing base Delphi types (which all map to arrays) using generics.

Florian Klaempfl
to Marco van de Voort
Marco van de Voort wrote 14 lines
In our previous episode, Florian Klaempfl said: >> Sorry, >> >> This was meant to be a private message. >> >> For those interested: the idea is to have a standard set of generics >> definitions that implement some commonly-used templates. A kind of STL >> in pascal. > > You are aware of the fgl unit in the rtl? It is supposed to be something > like this. The fgl unit seems more targeted at implementing base Delphi types (which all map to arrays) using generics.

Currently yes, but it was supposed to contain more types (Micha didn't continue ;)).