PopCnt of a buffer
lazarus / 64-FPC development

----------------------------------------------------------------------
LemonParty · 2025-10-13 09:01

Hello.

I suggest to add this function to standart units. Maybe to Math.
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i function
PopCnt(constref Buf; Count: SizeUInt): SizeUInt;var  p: PByte;  i:
SizeUInt;begin  Result:= 0;  if Count = 0 then    Exit;  i:=
Min(Count, SizeOf(SizeUInt) - 1 - (PtrUInt(@Buf) and (SizeOf(SizeUInt)
- 1)));  p:= @Buf;   {proceed unaligned begin}  if (i and 1) <> 0 then
begin    inc(Result, System.PopCnt(p^));    inc(p);  end;{$If
Defined(CPU32) or Defined(CPU64)}  if (i and 2) <> 0 then begin   
inc(Result, System.PopCnt(PWord(p)^));    inc(p, SizeOf(Word)); 
end;{$EndIf}{$IfDef CPU64}  if (i and 4) <> 0 then begin   
inc(Result, System.PopCnt(PDWord(p)^));    inc(p, SizeOf(DWord)); 
end;{$EndIf}  dec(Count, i);   {aligned reads in next loop}  for i:= 1
to Count div SizeOf(SizeUInt) do begin    inc(Result,
System.PopCnt(PSizeUInt(p)^));    inc(p, SizeOf(SizeUInt));  end;  
{proceed tail}{$IfDef CPU64}  if (Count and 4) <> 0 then begin   
inc(Result, System.PopCnt(PDWord(p)^));    inc(p, SizeOf(DWord)); 
end;{$EndIf}{$If Defined(CPU32) or Defined(CPU64)}  if (Count and 2)
<> 0 then begin    inc(Result, System.PopCnt(PWord(p)^));    inc(p,
SizeOf(Word));  end;{$EndIf}  if (Count and 1) <> 0 then begin   
inc(Result, System.PopCnt(p^));  end;end;

----------------------------------------------------------------------
Thaddy · 2025-10-13 10:46

No, because the code is not good enough.
Also, the defines make no sense. The compiler will optimize for the
cpu's.
Much simpler and not much slower is this:Code: Pascal
 [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i {$mode
objfpc}uses sysutils; function PopCnt(const Buf:Tbytes):
integer;overload;inline;var  a:byte;begin  Result:= 0;  for a in buf
do     inc(result, popcnt(a));end; function PopCnt(const
Buf;len:cardinal): integer;overload;inline;var  a:integer; 
p:PByte;begin  p:=@Buf;  Result:= 0;   for a := 0 to len-1 do   
 inc(result,popcnt(p[a]));end; var  test:string = 'ábcdefghij';begin 
writeln(popcnt(BytesOf(test))); 
writeln(popcnt(test[1],length(test)));end.The use case for an
optimized version takes a lot of bytes for not much gain.

----------------------------------------------------------------------
LemonParty · 2025-10-13 13:19

Quote from: Thaddy on October 13, 2025, 12:46:18 pmNo, because the
code is not good enough.
Also, the defines make no sense. The compiler will optimize for the
cpu's.
Much simpler and not much slower is this:Code: Pascal
 [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i {$mode
objfpc}uses sysutils; function PopCnt(const Buf:Tbytes):
integer;overload;inline;var  a:byte;begin  Result:= 0;  for a in buf
do     inc(result, popcnt(a));end; function PopCnt(const
Buf;len:cardinal): integer;overload;inline;var  a:integer; 
p:PByte;begin  p:=@Buf;  Result:= 0;   for a := 0 to len-1 do   
 inc(result,popcnt(p[a]));end; var  test:string = 'ábcdefghij';begin 
writeln(popcnt(BytesOf(test))); 
writeln(popcnt(test[1],length(test)));end.The use case for an
optimized version takes a lot of bytes for not much gain.

I just completed a simple benchmark that look like this:
Code: Pascal  [Select][+][-]window.onload = function(){var x1 =
document.getElementById("main_content_section"); if (x1) { var x =
document.getElementsByClassName("geshi");for (var i = 0; i  
SetLength(ArrA, 1024*1024);          sw.Start;  i:= PopCnt(ArrA[0],
Length(ArrA));  sw.Stop;  Writeln(sw.ElapsedTicks);   sw.Reset;
sw.Start;  i:= PopCntS(ArrA[0], Length(ArrA));  sw.Stop; 
Writeln(sw.ElapsedTicks); PopCntS is your version. I got results:
Quote12333
15077

12310
15707

12310
14814
Almost 25 % performance boost. Those defines are not useless, compiler
can't optimize such code by himself.

----------------------------------------------------------------------
runewalsh · 2025-10-13 15:35

Can you please describe the chain of events that led you to popcnting
the buffer?

----------------------------------------------------------------------
Thaddy · 2025-10-13 15:44

Yes, curious, especially on larger populations it makes almost no
sense.

----------------------------------------------------------------------
Thaddy · 2025-10-13 15:48

Quote from: LemonParty on October 13, 2025, 03:19:36 pmAlmost 25 %
performance boost. Those defines are not useless, compiler can't
optimize such code by himself.
You can leave the defines out! test on both CPU types...

----------------------------------------------------------------------
LemonParty · 2025-10-13 17:05

Quote from: runewalsh on October 13, 2025, 05:35:22 pmCan you please
describe the chain of events that led you to popcnting the buffer?
I am working with bitpacked arrays like Classes.TBits. There needed
this function.

QuoteYou can leave the defines out!Nope. I getting wrong results on
32-bit target without defines.

----------------------------------------------------------------------
runewalsh · 2025-10-13 17:27

What would you even need PopCnt for? For instance, if you're using a
bit field to count unique elements in a sequence (say, all elements
are between 0 and 999, soo 1000-bit bitfield will do), you don't need
PopCnt, you just read and write individual bits, and increment a
counter each time you changed a bit from 0 to 1.

----------------------------------------------------------------------
LemonParty · 2025-10-13 17:38

I use it for removing elements in given range. Instead of checking
every bit I can take a chunk of bits, and than use PopCnt to find
exact amount of setted bits in the chunk, then I zero this chunk and
move to next one.

----------------------------------------------------------------------
LemonParty · 2025-10-13 17:45

Also the same method is used to find the amount of elements that lie
in a given range.