Set size limit

classic Classic list List threaded Threaded
30 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Set size limit

Daniel Gaspary
Hi,

   I am trying to create a Set Type...

   TMyEnum = (me1, me2, me3); // more than 500 elements

   TMySet = set of TMyEnum;

...but I get the following error:

"Error: illegal type declaration of set elements" [1]

The problem seems to be that TMyEnum has more than 256 elements.

Can I specify such Set with some compiler option ?

My fpc is pre 2.6, any change on new versions concerning Sets limits?

Thanks.

[1] A more specific message would help too. :)
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Set size limit

Jonas Maebe-2

On 09 Mar 2013, at 21:52, Daniel Gaspary wrote:

The problem seems to be that TMyEnum has more than 256 elements.

Can I specify such Set with some compiler option ?

No.

My fpc is pre 2.6, any change on new versions concerning Sets limits?

No.


Jonas

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Set size limit

Graeme Geldenhuys-3
In reply to this post by Daniel Gaspary
On 2013-03-09 20:52, Daniel Gaspary wrote:
>
> The problem seems to be that TMyEnum has more than 256 elements.
> Can I specify such Set with some compiler option ?

No.  As far as I understand, sets are stored in 1 byte internally - as
binary values. 256 is the max number of elements (bit values) it can
hold in a byte.


Regards,
  - Graeme -

--
fpGUI Toolkit - a cross-platform GUI toolkit using Free Pascal
http://fpgui.sourceforge.net/

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Set size limit

Marco van de Voort
In our previous episode, Graeme Geldenhuys said:
> On 2013-03-09 20:52, Daniel Gaspary wrote:
> >
> > The problem seems to be that TMyEnum has more than 256 elements.
> > Can I specify such Set with some compiler option ?
>
> No.  As far as I understand, sets are stored in 1 byte internally - as
> binary values. 256 is the max number of elements (bit values) it can
> hold in a byte.

Sets are up to 32-byte (256bits), enums can be up to 32-bit.
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Set size limit

Juha Manninen
In reply to this post by Graeme Geldenhuys-3
On Sun, Mar 10, 2013 at 2:38 PM, Graeme Geldenhuys
<[hidden email]> wrote:
> No.  As far as I understand, sets are stored in 1 byte internally - as
> binary values. 256 is the max number of elements (bit values) it can
> hold in a byte.

This is one area where FPC could actually improve things.
The 1 byte limit is purely historical. There are no 8-bit CPUs
supported by FPC that would justify it.

I am annoyed by some LCL bugs which are there only for Delphi compatibility.
This issue is similar. This kind of artificial limitation could easily be fixed.
I think it should apply for {$mode objfpc} only.

Juha
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Set size limit

Jonas Maebe-2

On 10 Mar 2013, at 15:00, Juha Manninen wrote:

> There are no 8-bit CPUs
> supported by FPC that would justify it.

It is unrelated to 8 bit cpus. Even Turbo Pascal 1.0 ran on a 16 bit cpu.

> I am annoyed by some LCL bugs which are there only for Delphi compatibility.
> This issue is similar.

It is not.

> This kind of artificial limitation could easily be fixed.
> I think it should apply for {$mode objfpc} only.

There is a already a test for larger set support: http://svn.freepascal.org/svn/fpc/trunk/tests/test/tset6.pp

Nobody has worked yet on implementing it, but if anyone thinks it's easy to do, please go ahead. For larger sets, especially if they are sparse, a simple hashtable-based class would probably be much faster and memory efficient than simply extending the default implementation though. With operator overloading and generics you might even be able to use more or less the same syntax as with built-in sets.


Jonas_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Set size limit

Juha Manninen
In reply to this post by Marco van de Voort
On Sun, Mar 10, 2013 at 3:45 PM, Marco van de Voort <[hidden email]> wrote:
> Sets are up to 32-byte (256bits), enums can be up to 32-bit.

Ok, sorry. The limitation for sets is not one byte.
Still, FPC could add support for still more bytes. 64-bit CPUs are now
popular and the feature could easily be implemented for other CPUs,
too.

Regards,
Juha
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Set size limit

Florian Klämpfl
In reply to this post by Juha Manninen
Am 10.03.2013 15:00, schrieb Juha Manninen:
> This issue is similar. This kind of artificial limitation

I always wonder how people know more than me about the compiler :)

> could easily be fixed.

Go ahead.

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Set size limit

Daniel Gaspary
In reply to this post by Jonas Maebe-2
On Sun, Mar 10, 2013 at 11:12 AM, Jonas Maebe <[hidden email]> wrote:
> For larger sets, especially if they are sparse, a simple hashtable-based class
> would probably be much faster and memory efficient

Just some background..

I was using a Set because I needed a initialized constant "container"
with a variable length.

It was a array of records, the set would be one of the fields. I
believe it's not possible to have dynamic array initialized inside
records.

TMyRecord = record
   TheSet: TMySet;
end;

const
        MyArray: array[TMyEnum] of TMyRecord = ( (TheSet: [me1, me3]),
(TheSet: [me2, me1]) );

Now I have changed the code to a function with a case returning the record.
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Set size limit

Juha Manninen
In reply to this post by Florian Klämpfl
On Sun, Mar 10, 2013 at 4:19 PM, Florian Klämpfl <[hidden email]> wrote:
>> This issue is similar. This kind of artificial limitation
> I always wonder how people know more than me about the compiler :)
>
>> could easily be fixed.
> Go ahead.

:)
Ok, I sent my reply too quickly. I must study the compiler at some day.
I must say that I don't like the situation where I cannot backup my
claims with facts.
Now I cannot. I sill study the compiler later ...

Regards,
Juha
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Set size limit

Howard Page-Clark
In reply to this post by Jonas Maebe-2
On 10/03/13 2:12, Jonas Maebe wrote:

> There is a already a test for larger set support: http://svn.freepascal.org/svn/fpc/trunk/tests/test/tset6.pp
>
> Nobody has worked yet on implementing it, but if anyone thinks it's easy to do, please go ahead. For larger sets,
  especially if they are sparse, a simple hashtable-based class would
probably be much faster and memory efficient
  than simply extending the default implementation though. With operator
overloading and generics you might even be
  able to use more or less the same syntax as with built-in sets.

There is a generic hashset implementation in the stl package, which has
no 256-element limit on set size. See
...\source\packages\fcl-stl\src\ghashset.pp
A .tex documentation file is included along with a hashsetexample.pp

Howard

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Set size limit

Rolf Grunsky
In reply to this post by Jonas Maebe-2
On 13-03-09 03:56 PM, Jonas Maebe wrote:

>
> On 09 Mar 2013, at 21:52, Daniel Gaspary wrote:
>
>> The problem seems to be that TMyEnum has more than 256 elements.
>>
>> Can I specify such Set with some compiler option ?
>
> No.
>
>> My fpc is pre 2.6, any change on new versions concerning Sets limits?
>
> No.
>
>
> Jonas
>
>
> _______________________________________________
> fpc-pascal maillist  -  [hidden email]
> http://lists.freepascal.org/mailman/listinfo/fpc-pascal
>
As I recall (it's been almost 30 years since I looked at this) UCSD
Pascal had a set size of 4096 bits. This was a p-code interpreter. I
think the 32 bit set size was a result of the original TurboPascal being
written for the Z-80. UCSD Pascal is long gone, TurboPascal staggers on.

Rolf

--
                                TRUTH in her dress finds facts too tight.
                                In fiction she moves with ease.
                                Stray Birds by Rabindranath Tagore
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Set size limit

Mark Morgan Lloyd-5
In reply to this post by Juha Manninen
Juha Manninen wrote:

>> No.  As far as I understand, sets are stored in 1 byte internally - as
>> binary values. 256 is the max number of elements (bit values) it can
>> hold in a byte.
>
> This is one area where FPC could actually improve things.
> The 1 byte limit is purely historical. There are no 8-bit CPUs
> supported by FPC that would justify it.
>
> I am annoyed by some LCL bugs which are there only for Delphi compatibility.
> This issue is similar. This kind of artificial limitation could easily be fixed.

Without wanting to cause upset, before you make statements like that I
think you could /really/ do with checking how many bits fit in a byte :-)

--
Mark Morgan Lloyd
markMLl .AT. telemetry.co .DOT. uk

[Opinions above are the author's, not those of his employers or colleagues]
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Set size limit

Mark Morgan Lloyd-5
In reply to this post by Jonas Maebe-2
Jonas Maebe wrote:
> On 10 Mar 2013, at 15:00, Juha Manninen wrote:
>
>> There are no 8-bit CPUs
>> supported by FPC that would justify it.
>
> It is unrelated to 8 bit cpus. Even Turbo Pascal 1.0 ran on a 16 bit cpu.

Provided that one calls a Z80 16-bit :-) More to the point: do any
current CPUs have e.g. vector operations that suggest a realistic
maximum size?

>> I am annoyed by some LCL bugs which are there only for Delphi compatibility.
>> This issue is similar.
>
> It is not.
>
>> This kind of artificial limitation could easily be fixed.
>> I think it should apply for {$mode objfpc} only.
>
> There is a already a test for larger set support: http://svn.freepascal.org/svn/fpc/trunk/tests/test/tset6.pp
>
> Nobody has worked yet on implementing it, but if anyone thinks it's easy to do, please go ahead. For larger sets, especially if they are sparse, a simple hashtable-based class would probably be much faster and memory efficient than simply extending the default implementation though. With operator overloading and generics you might even be able to use more or less the same syntax as with built-in sets.

For larger sets... OK, how /does/ one declare a set of UTF-8 characters?

--
Mark Morgan Lloyd
markMLl .AT. telemetry.co .DOT. uk

[Opinions above are the author's, not those of his employers or colleagues]
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Set size limit

Jonas Maebe-2

On 11 Mar 2013, at 10:39, Mark Morgan Lloyd wrote:

> Jonas Maebe wrote:
>> On 10 Mar 2013, at 15:00, Juha Manninen wrote:
>>> There are no 8-bit CPUs
>>> supported by FPC that would justify it.
>> It is unrelated to 8 bit cpus. Even Turbo Pascal 1.0 ran on a 16  
>> bit cpu.
>
> Provided that one calls a Z80 16-bit :-) More to the point: do any  
> current CPUs have e.g. vector operations that suggest a realistic  
> maximum size?

The current x86's bit test/set instructions support addressing the  
complete 32/64 bit address space. But the original 8086 didn't have  
any vector instructions at all. Again: this limitation is unrelated to  
instruction sets, it's about deciding on a point at which you're going  
to waste a lot of memory by using a plain bitmap.

>> There is a already a test for larger set support: http://svn.freepascal.org/svn/fpc/trunk/tests/test/tset6.pp
>> Nobody has worked yet on implementing it, but if anyone thinks it's  
>> easy to do, please go ahead. For larger sets, especially if they  
>> are sparse, a simple hashtable-based class would probably be much  
>> faster and memory efficient than simply extending the default  
>> implementation though. With operator overloading and generics you  
>> might even be able to use more or less the same syntax as with  
>> built-in sets.
>
> For larger sets... OK, how /does/ one declare a set of UTF-8  
> characters?

An UTF-8 character is not an ordinal data type and hence support for  
"set of <utf-8 character>" is orthogonal to support for larger sets.  
If you store them in strings or arrays, then you need a hashtable of  
strings or arrays (and/or support for sets of strings or arrays, which  
would probably be implemented using... a hashtable).


Jonas
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Set size limit

Mark Morgan Lloyd-5
Jonas Maebe wrote:

>> Provided that one calls a Z80 16-bit :-) More to the point: do any
>> current CPUs have e.g. vector operations that suggest a realistic
>> maximum size?
>
> The current x86's bit test/set instructions support addressing the
> complete 32/64 bit address space. But the original 8086 didn't have any
> vector instructions at all. Again: this limitation is unrelated to
> instruction sets, it's about deciding on a point at which you're going
> to waste a lot of memory by using a plain bitmap.

>> For larger sets... OK, how /does/ one declare a set of UTF-8 characters?
>
> An UTF-8 character is not an ordinal data type and hence support for
> "set of <utf-8 character>" is orthogonal to support for larger sets. If
> you store them in strings or arrays, then you need a hashtable of
> strings or arrays (and/or support for sets of strings or arrays, which
> would probably be implemented using... a hashtable).

That was pretty much my gist. Since these days Unicode is larger than
65536 codepoints I don't think there's any advantage to expanding sets
from 256 to 65536 elements, efficient operations on sparse arrays of
256-element sets would be far better.

A modest expansion to be able to handle something like a bitboard for Go
might be attractive though.

--
Mark Morgan Lloyd
markMLl .AT. telemetry.co .DOT. uk

[Opinions above are the author's, not those of his employers or colleagues]
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Set size limit

Daniel Gaspary
On Mon, Mar 11, 2013 at 7:09 AM, Mark Morgan Lloyd
<[hidden email]> wrote:
> That was pretty much my gist. Since these days Unicode is larger than 65536
> codepoints I don't think there's any advantage to expanding sets from 256 to
> 65536 elements, efficient operations on sparse arrays of 256-element sets
> would be far better.

In my case the enum has near 600 elements.

TMyEnum = (me1, me2...);

The set though would never be used to contain more than 256.

TMySet = set of TMyEnum;

Is it not viable to modify the compiler to compile the code and raise
an exception if I try to add more than 256 elements to the set ?
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Set size limit

Jonas Maebe-2

On 11 Mar 2013, at 14:32, Daniel Gaspary wrote:

In my case the enum has near 600 elements.

TMyEnum = (me1, me2...);

The set though would never be used to contain more than 256.

TMySet = set of TMyEnum;

Is it not viable to modify the compiler to compile the code and raise
an exception if I try to add more than 256 elements to the set ?

A set is basically a bitpacked array of boolean. Element X is set to true if you add X to the set, and to false if you remove it again. That means that if you have a set with 600 possible values, you need at least 600 bits, regardless of how many elements are inside it.

The above also shows an alternative to sets in that case: you can use a bitpacked array[TMyEnum] of boolean instead. Of course, then you can't use the regular set operators.


Jonas

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Set size limit

Sven Barth-2
Am 11.03.2013 14:43, schrieb Jonas Maebe:

On 11 Mar 2013, at 14:32, Daniel Gaspary wrote:

In my case the enum has near 600 elements.

TMyEnum = (me1, me2...);

The set though would never be used to contain more than 256.

TMySet = set of TMyEnum;

Is it not viable to modify the compiler to compile the code and raise
an exception if I try to add more than 256 elements to the set ?

A set is basically a bitpacked array of boolean. Element X is set to true if you add X to the set, and to false if you remove it again. That means that if you have a set with 600 possible values, you need at least 600 bits, regardless of how many elements are inside it.

The above also shows an alternative to sets in that case: you can use a bitpacked array[TMyEnum] of boolean instead. Of course, then you can't use the regular set operators.
If the array is a named one (e.g. "TMyArraySet = bitpacked array[TMyEnum] of Boolean") then operator overloading could be used...

Regards,
Sven

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Set size limit

Daniel Gaspary
In reply to this post by Jonas Maebe-2
On Mon, Mar 11, 2013 at 10:43 AM, Jonas Maebe <[hidden email]> wrote:

> A set is basically a bitpacked array of boolean. Element X is set to true if
> you add X to the set, and to false if you remove it again. That means that
> if you have a set with 600 possible values, you need at least 600 bits,
> regardless of how many elements are inside it.
>
> The above also shows an alternative to sets in that case: you can use a
> bitpacked array[TMyEnum] of boolean instead. Of course, then you can't use
> the regular set operators.
>
> Jonas

Your explanation made the implementation problem clear to me. And the
alternative is interesting.

Thank you.
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
12