Recent

Author Topic: Optimize TDeque.IncreaseCapacity  (Read 7708 times)

Thaddy

  • Hero Member
  • *****
  • Posts: 14204
  • Probably until I exterminate Putin.
Re: Optimize TDeque.IncreaseCapacity
« Reply #15 on: October 14, 2018, 08:06:38 pm »
What about my change?
The many branches in that code would make it slower than the current implementation.
Either use a look-up or stick to your original plan and increase the initial size to say, 4 or 5.

You have to devise some tests...
Specialize a type, not a var.

Artem3213212

  • New member
  • *
  • Posts: 7
Re: Optimize TDeque.IncreaseCapacity
« Reply #16 on: October 14, 2018, 08:45:12 pm »
What about my change?
Ok, but it make some bad work with memory pages. Correct version:
Code: Pascal  [Select][+][-]
  1. procedure TDeque.IncreaseCapacity;
  2. const
  3.   // if size is small, multiply by 2;
  4.   // if size bigger but <256M, inc by 1/8*size;
  5.   // otherwise inc by 1/16*size
  6.   cSizeSmall = 1*1024*1024;
  7.   cSizeBig = 256*1024*1024;
  8. var
  9.   i,OldEnd:SizeUInt;
  10.   DataSize:SizeUInt;
  11. begin
  12.   OldEnd:=FCapacity;
  13.  
  14.   DataSize:=FCapacity*SizeOf(T);
  15.   if FCapacity=0 then
  16.     FCapacity:=4
  17.   else
  18.   if DataSize<cSizeSmall then
  19.     FCapacity*=2
  20.   else
  21.   if DataSize<cSizeBig then
  22.     FCapacity+=FCapacity div 8 and $FFFFF000
  23.   else
  24.     FCapacity+=FCapacity div 16 and $FFFFF000;
  25.  
  26.   SetLength(FData, FCapacity);
  27.   if (FStart>0) then
  28.     for i:=0 to FStart-1 do
  29.       FData[OldEnd+i]:=FData[i];
  30. end;
  31.  
« Last Edit: October 14, 2018, 08:55:41 pm by Artem3213212 »

AlexTP

  • Hero Member
  • *****
  • Posts: 2386
    • UVviewsoft
Re: Optimize TDeque.IncreaseCapacity
« Reply #17 on: October 14, 2018, 08:48:59 pm »
Thaddy,
branches are needed here, to check: n in one of ranges:
[0..1M] [1M..256M] [256M..inf]

ASerge

  • Hero Member
  • *****
  • Posts: 2222
Re: Optimize TDeque.IncreaseCapacity
« Reply #18 on: October 17, 2018, 09:29:25 pm »
I like TFPList.Expand

Bart

  • Hero Member
  • *****
  • Posts: 5275
    • Bart en Mariska's Webstek
Re: Optimize TDeque.IncreaseCapacity
« Reply #19 on: January 06, 2021, 12:57:17 pm »
These changes to TDeque have broken it.
If the array isn't doubled (in IncreaseCapacity) then it is not circular anymore (the calculation of the positions wehre to put/get values doesn't match anymore.
See Issue #38306.

Bart

 

TinyPortal © 2005-2018