Recent

Author Topic: What happened to the built in CARD() function?  (Read 12887 times)

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11383
  • FPC developer.
Re: What happened to the built in CARD() function?
« Reply #15 on: February 11, 2018, 01:09:55 pm »
The use of qwords is an internal and legal for any bit set > 32 bits. It merely uses the most efficient available PopCnt overload.

Code: Pascal  [Select][+][-]
  1. {$mode delphi}
  2.  
  3. type  txxx = set of 0..247;
  4.  
  5. begin
  6.   writeln(sizeof(txxx));
  7. end.

Prints 31.

Thaddy

  • Hero Member
  • *****
  • Posts: 14203
  • Probably until I exterminate Putin.
Re: What happened to the built in CARD() function?
« Reply #16 on: February 11, 2018, 01:43:13 pm »
Prints 31.
https://www.freepascal.org/docs-html/ref/refsu16.html#x40-580003.3.3
" The compiler stores small sets (less than 32 elements) in a Longint, if the type range allows it. This allows for faster processing and decreases program size. Otherwise, sets are stored in 32 bytes."
The docs are wrong anyway since it should read less than 33 bits since set of 0..31 is size 4.

Maybe file a bug report against documentation?
« Last Edit: February 11, 2018, 01:46:56 pm by Thaddy »
Specialize a type, not a var.

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11383
  • FPC developer.
Re: What happened to the built in CARD() function?
« Reply #17 on: February 11, 2018, 01:49:27 pm »
https://www.freepascal.org/docs-html/ref/refsu16.html#x40-580003.3.3
" The compiler stores small sets (less than 32 elements) in a Longint, if the type range allows it. This allows for faster processing and decreases program size. Otherwise, sets are stored in 32 bytes."

True for mode objfpc, but not for delphi.  IIRC before the bytewise growing, Delphi mode already had a while that sets were multiples of 4 (might still be on non x86). That might go back as far as 2.2


documentation bug filed: https://bugs.freepascal.org/view.php?id=33156
« Last Edit: February 11, 2018, 01:52:31 pm by marcov »

ASerge

  • Hero Member
  • *****
  • Posts: 2222
Re: What happened to the built in CARD() function?
« Reply #18 on: February 11, 2018, 02:04:05 pm »
" The compiler stores small sets (less than 32 elements) in a Longint, if the type range allows it. This allows for faster processing and decreases program size. Otherwise, sets are stored in 32 bytes."
I think the documentation is inaccurate and most likely in FPC, as in Delphi: Max div 8 - Min div 8 + 1.

howardpc

  • Hero Member
  • *****
  • Posts: 4144
Re: What happened to the built in CARD() function?
« Reply #19 on: February 11, 2018, 02:11:20 pm »
After a bit more thought, a simplified Card() is this:
Code: Pascal  [Select][+][-]
  1. {$Mode objfpc}
  2.  
  3. type
  4.  
  5.   TMediumSetDWords = array[0..7] of DWord;
  6.  
  7. function Card(const aSet): Word;
  8. var
  9.   msdw: TMediumSetDWords absolute aSet;
  10.   b: Byte;
  11. begin
  12.   Result := PopCnt(msdw[0]);
  13.   for b := 1 to 7 do
  14.     Inc(Result, PopCnt(msdw[b]));
  15. end;
« Last Edit: February 11, 2018, 02:17:05 pm by howardpc »

Thaddy

  • Hero Member
  • *****
  • Posts: 14203
  • Probably until I exterminate Putin.
Re: What happened to the built in CARD() function?
« Reply #20 on: February 11, 2018, 02:46:46 pm »
After a bit more thought, a simplified Card() is this:
- That code is less efficient on modern processors since PopCnt has a qword option (like I used)
- It will - just like my own code - fail when called on a set that is stack allocated, i.e. from within a procedure or function. Unused bytes are "dirty".
- And as Marco demonstrates it will always fail in {$mode delphi}. The unused bytes are undefined, i.e. also dirty.

Without a means of determining the size of the set inside a function and from an un-typed const it seems impossible to write a typesafe generic card function as it stands using high-level code. For small sets it works though:
Code: Pascal  [Select][+][-]
  1. // card for sets with 32 elements or less.
  2. function card(const s):integer;
  3. begin
  4.   card := PopCnt(Dword(s));
  5. end;

For the compiler it should not be any problem to introduce such a feature since it knows the size of the set at compile time. This looks only solvable with compiler magic. (Just like PopCnt)
« Last Edit: February 11, 2018, 02:49:24 pm by Thaddy »
Specialize a type, not a var.

PascalDragon

  • Hero Member
  • *****
  • Posts: 5446
  • Compiler Developer
Re: What happened to the built in CARD() function?
« Reply #21 on: February 17, 2018, 07:32:02 pm »
Generic functions to the rescue:

Code: Pascal  [Select][+][-]
  1. program tcard;
  2.  
  3. {$mode objfpc}
  4.  
  5. generic function Card<T>(aSetValue: T): LongInt;
  6. var
  7.   i: LongInt;
  8. begin
  9.   if SizeOf(aSetValue) <= 4 then
  10.     Result := PopCnt(PLongWord(@aSetValue)^)
  11.   else begin
  12.     Result := 0;
  13.     for i := 0 to SizeOf(aSetValue) div SizeOf(LongWord) - 1 do
  14.       Inc(Result, PopCnt(PLongWord(@aSetValue)[i]));
  15.   end;
  16. end;
  17.  
  18. type
  19.   TSet1 = set of 1..3;
  20.   TSet2 = set of 1..40;
  21.  
  22. var
  23.   set1: TSet1;
  24.   set2: TSet2;
  25. begin
  26.   set1 := [2];
  27.   set2 := [4, 9, 23, 40];
  28.  
  29.   Writeln(specialize Card<TSet1>(set1));
  30.   Writeln(specialize Card<TSet2>(set2));
  31. end.
  32.  

Sadly the "Unreachable code" warning can not be suppressed  :'(

ASerge

  • Hero Member
  • *****
  • Posts: 2222
Re: What happened to the built in CARD() function?
« Reply #22 on: February 17, 2018, 09:28:58 pm »
Sadly the "Unreachable code" warning can not be suppressed  :'(
1. This is compiled only in the development version.
2. With {$mode objfpc} only two set sizes: 4 and 32. Thus, either one or the other part of "if" is an unreachable code.
3. With {$mode delphi} this code, with little modification, is wrong, because, as @Thaddy say "The unused bytes are undefined, i.e. also dirty".
Code: Pascal  [Select][+][-]
  1. program Project1;
  2. {$APPTYPE CONSOLE}
  3.  
  4. {-$mode delphi}
  5. {$mode objfpc}
  6.  
  7. {$IFDEF FPC_OBJFPC}generic{$ENDIF}
  8. function Card<T>(const aSetValue: T): Integer;
  9. var
  10.   i: Integer;
  11. begin
  12.   Result := 0;
  13.   for i := 0 to SizeOf(T) - 1 do
  14.     Inc(Result, PopCnt(PByte(@aSetValue)[i]));
  15. end;
  16.  
  17. type
  18.   TSet1 = set of 0..3;
  19.   TSet2 = set of 0..40;
  20.  
  21. var
  22.   set1: TSet1 = [2];
  23.   set2: TSet2 = [4, 9, 23, 40];
  24. begin
  25.   set1 := [2];
  26.   set2 := [4, 9, 23, 40];
  27.  
  28.   Writeln(SizeOf(TSet1));
  29.   Writeln(SizeOf(TSet2));
  30.   Writeln({$IFDEF FPC_OBJFPC}specialize {$ENDIF}Card<TSet1>(set1));
  31.   Writeln({$IFDEF FPC_OBJFPC}specialize {$ENDIF}Card<TSet2>(set2));
  32.   Readln;
  33. end.
« Last Edit: February 17, 2018, 09:55:44 pm by ASerge »

PascalDragon

  • Hero Member
  • *****
  • Posts: 5446
  • Compiler Developer
Re: What happened to the built in CARD() function?
« Reply #23 on: February 18, 2018, 11:36:32 am »
Sadly the "Unreachable code" warning can not be suppressed  :'(
1. This is compiled only in the development version.
So? A potential Card() function or intrinsic would also only be part of trunk.
2. With {$mode objfpc} only two set sizes: 4 and 32. Thus, either one or the other part of "if" is an unreachable code.
Yes, I know, but I'm more complaining about that even with {$warn off 6018} around the generic function the compiler doesn't remember that setting when specializing the function which is quite irritating, cause I thought that this should work. Probably a bug I'll have to look at... *sigh*
3. With {$mode delphi} this code, with little modification, is wrong, because, as @Thaddy say "The unused bytes are undefined, i.e. also dirty".
Code: Pascal  [Select][+][-]
  1. program Project1;
  2. {$APPTYPE CONSOLE}
  3.  
  4. {-$mode delphi}
  5. {$mode objfpc}
  6.  
  7. {$IFDEF FPC_OBJFPC}generic{$ENDIF}
  8. function Card<T>(const aSetValue: T): Integer;
  9. var
  10.   i: Integer;
  11. begin
  12.   Result := 0;
  13.   for i := 0 to SizeOf(T) - 1 do
  14.     Inc(Result, PopCnt(PByte(@aSetValue)[i]));
  15. end;
  16.  
  17. type
  18.   TSet1 = set of 0..3;
  19.   TSet2 = set of 0..40;
  20.  
  21. var
  22.   set1: TSet1 = [2];
  23.   set2: TSet2 = [4, 9, 23, 40];
  24. begin
  25.   set1 := [2];
  26.   set2 := [4, 9, 23, 40];
  27.  
  28.   Writeln(SizeOf(TSet1));
  29.   Writeln(SizeOf(TSet2));
  30.   Writeln({$IFDEF FPC_OBJFPC}specialize {$ENDIF}Card<TSet1>(set1));
  31.   Writeln({$IFDEF FPC_OBJFPC}specialize {$ENDIF}Card<TSet2>(set2));
  32.   Readln;
  33. end.
Yes, that definitely simplifies that affair without any unreachable code warning. I was much too focused on the difference between small and large sets plus I wasn't aware that PopCnt had an overload for Byte as I had no need to use that function before.  :-[

Small additional improvement: Unlike Delphi FPC can also make use of "inline" here as long as the method implementation is encountered before it is first called (e.g. in the case above that works).  :D

 

TinyPortal © 2005-2018