Can Sets be used to skip array items? [Solved]

[mas steindorff]

I want to thank both of you (Thaddy and Mr.Madguy)  for going into the low level details like you have.  this is what I was hoping to learn.  When I was doing D4 on a 286 CPU, I tested SETS vis the mask approach and found SETS were slower. However, I have noted a lot of extend table and math instructions have developed in the newer CPU command sets over the years.  if SETs even run close to the mask approach then it's resulting readability works as a tie breaker.  I did not even think of using...

Code: [Select]

for i in Myset do ...    
probably due to my avoidance of SETs. 
as a side query: I know C++ supports SETS but do any of you know if it's supported in normal C? 

[Thaddy]

- Sets are implemented using masks... as the compiler output showed in using bitwise operants.
- No, plain C does not have sets (as C++ also doesn't: it is implemented in C++ on library level, not compiler level like in Pascal)

You can be assured that sets run about as fast as a mask approach: they are the same beast.

Both Mr.MadGuy and me like to examine what the compiler actually does...

[marcov]

  When I was doing D4 on a 286 CPU, I tested SETS vis the mask approach and found SETS were slower.

Interesting! How did you get a 32-bit Delphi 4 working on a 16-bit processor?

P.s. performance between registrable and non register sets can be quite noticeable.

[Thaddy]

Indeed. I missed that 
Anyway, to my recollection sets have never been slower than masking. It is the same. Proper use of Boolean logic. Wirthian languages.

[Thaddy]

In general, sets have always been a strength of Pascal over languages like C. I may be somewhat biased but I like them a lot. And my main programming is NOT done in Pascal.

[mas steindorff]

  When I was doing D4 on a 286 CPU, I tested SETS vis the mask approach and found SETS were slower.

Interesting! How did you get a 32-bit Delphi 4 working on a 16-bit processor?

P.s. performance between registrable and non register sets can be quite noticeable.

you are right, It may have been a 386sx but it was an early Delphi and not Turbo Pascal. 

The test was part of a comparison between the different PCs on the market and included some matrix math. The original was in C.  I re-coded it in pascal and added some other testing to make a benchmark program.  I do remember everyone amazed at how the pascal was 2 to 4 times faster than the C code in this area.  I had to show I was doing the matrix math correctly as I (a hardware/firmware guy) had inadvertently bested the best efforts of the PC software programming group in just a few weeks.

thus my love for pascal grows...

[engkin]

Considering that all the solutions above would have to loop 30 times regardless of the number of items that need to be filtered, I think there is a faster way.

Save the needed indices and their count:

Code: Pascal  [Select][+][-]

1. var
2.   indexes: array[0..29] of integer;
3.   Count: integer;
4.  
5. procedure f1_;
6. var i:byte;
7.  begin
8.   Count := 0;
9.   for i:= 1 to 30 do begin
10.     if (testForSkip(i)) then
11.     begin
12.        indexes[Count] := i;
13.        inc(Count);
14.     end;
15.    end;
16. end;
17.  
18. function f2_(sarray:array of double):integer;
19. var
20.      c:integer;
21. begin
22.   for c:= 0 to Count-1 do begin
23.         final[c] := sarray[indexes[c]];
24.        end;
25.   result := Count;
26. end;

[PascalDragon]

In general, sets have always been a strength of Pascal over languages like C. I may be somewhat biased but I like them a lot. And my main programming is NOT done in Pascal.

Sets are one of the features I really miss when working with C++ at work (one of the others being virtual class methods).

[egsuh]

Why not the simplest?

Code: Pascal  [Select][+][-]

1. function CopyFilteredArray(sarray: array of double): integer;
2. var
3.   i : integer;
4. begin
5.   Result := 0;
6.   for i:= Low(sarray) to High(sarray) do  
7.      if not testforskip(i) then begin
8.         final[Result] = sarray[i];      // or doSomething(sarray[i])
9.         inc(Result);
10.      end
11.      else include(skipset, i);  // if you need skipset later
12. end;

[mas steindorff]

Why not the simplest?

in my case, the testforskip() was complex and only needed to one once before the data started streaming.

So in the end I found I needed both a SET and a bit mask to keep thing fast so I created an object that holds one of each.  then when I added a channel, a bit in the mask would also be set and vis versa.  here is my code to share for this topic since all of you helped.
<FYI this code is not yet tested>

Code: [Select]

type
  TChanListSets = object
    private  { private declarations }
      MySlots : PktDataSlots;
      MyMask  : U32;
   procedure SetMask(AValue: U32);
   procedure SetSlots(AValue: PktDataSlots);
    public    { public declarations }
      count : Integer;
      property  Slots : PktDataSlots read MySlots write SetSlots;
      property  Mask  : U32 read MyMask write SetMask;
      procedure AddChan(ch:Integer);
      procedure RemoveChan(ch:Integer);
      procedure Clear();
  end;

...

procedure TChanListSets.Clear();
begin
  MyMask := 0;
  count  := 0;
  MySlots:= []; // empty set
end;

procedure TChanListSets.SetMask(AValue: U32);
var i,msk :U32;
begin
   Avalue := (Avalue and CHANNEL_MSK_24);
   if MyMask =AValue then
      Exit;
   MyMask :=AValue;
   MySlots :=[];   // empty set
   count := 0;
   if (Avalue = 0) then
      exit;
  // removed some predefined sets here that were commonly used that just set the SET and Mask
 // <snip>
   msk := 1;
   i   := 1;
   repeat
     if ((msk and Avalue)>0) then begin
        Avalue := Avalue xor msk; // clr the bit
        Include(MySlots, i);
        inc(count);
        end;
     msk := msk shl 1;
  inc(i);
until (avalue = 0) or (i > 30);
end;

procedure TChanListSets.SetSlots(AValue: PktDataSlots);  // set SETs to a value
var i :Integer;
begin
   if MySlots = AValue then
      Exit;
   MySlots :=AValue;
   MyMask  := 0;
   count := 0;
   for i in MySlots do begin              // keep the mask in sync
      MyMask :=MyMask or (1 shl i-1);
      inc(count);
end;
end;

procedure TChanListSets.AddChan(ch: Integer);
var msk:U32;
begin
   if (ch < 1) or (ch > MaxCalChannels) then begin
      Exception.Create('channel value of '+IntToStr(ch)+' Out Of Range[1..30]');
      exit;
      end;
   msk := MyMask;
   MyMask := MyMask or (1 shl ch-1);
   if (msk = MyMask) then
      exit;
   Include(MySlots,ch);
   inc(count);
end;

procedure TChanListSets.RemoveChan(ch: Integer);
var msk:U32;
begin
   if (ch < 1) or (ch > MaxCalChannels) then begin
      Exception.Create('channel value of '+IntToStr(ch)+' Out of Range[1..30]');
      exit;
      end;
   msk := MyMask;
   MyMask := MyMask and not(1 shl ch-1);
   if (msk = MyMask) then
      exit;
   Exclude(MySlots,ch);
   dec(count);
end;


Now I have both a list of channels and a channel mask I can use in my final code. I used an object instead of a class due to the fact it will be included in another class and I do not need a separate create() or destroy() yet.

[egsuh]

I have done similar tests in the past. My conclusion was to use TStringList.  This is faster than arrays or sets.

First construct Mask TStringList.

Mask := TStringList.Create;
Mask.Sorted := True;

for i:= 1 to 30 do
    if testforskip then mask.add (inttostr(i));

Then another TStringList.

Channels := TStringList.Create;
for i := 1 to 30 do
    if Mask.IndexOf(IntTostr(Values)) = -1 then Channels.Add(IntTostr(Values));

Or you may the reverse.

Channels := TStringList.Create;
for i := 1 to 30 do  Channels.Add(values);
for i:= 0 to Mask.Count-1 do Channels.Delete(Channels.IndexOf(Mask));

I suggest this as one option. I experimented various options, but always TStrings were the fastest. (in Delphi...)

[Mr.Madguy]

I suggest this as one option. I experimented various options, but always TStrings were the fastest. (in Delphi...)

Sorry, but this looks like Indian programming on a par with this:

Code: Pascal  [Select][+][-]

1. var X:Boolean;
2. if Length(X.ToString) < 5 then begin
3. ...
4. end;
5.  

1) Integer operations are always faster, than string operations.
2) List is always slower due to memory allocations, reallocations, deallocations and copying.

[Thaddy]

Sets are always faster than strings. Much faster.

[egsuh]

Sets are always faster than strings. Much faster.

Should be.
Probably my experiments were mostly with dynamic arrays. I couldn't use sets because I had use integer values larger than 255.  Still I expected integers are faster, but result was not.