Lazarus

Free Pascal => General => Topic started by: AlexTP on October 13, 2018, 09:55:33 pm

Title: Optimize TDeque.IncreaseCapacity
Post by: AlexTP on October 13, 2018, 09:55:33 pm
Code: Pascal  [Select][+][-]
  1. procedure TDeque.IncreaseCapacity;inline;
  2. var i,OldEnd:SizeUInt;
  3. begin
  4.   OldEnd:=FCapacity;
  5.   if(FCapacity=0) then
  6.     FCapacity:=1
  7.   else
  8.     FCapacity:=FCapacity*2;
  9.   SetLength(FData, FCapacity);
  10.   if (FStart>0) then
  11.     for i:=0 to FStart-1 do
  12.       FData[OldEnd+i]:=FData[i];
  13. end;

suggestion: make first value not 1 but cInitialCapacity (const in unit).
Set it not to 1 but to 4, or better 8.
Title: Re: Optimize TDeque.IncreaseCapacity
Post by: Thaddy on October 14, 2018, 08:31:40 am
The TQueue<T> from generics.collections has optimal memory expansion.
Instead of the naive quadratic approach it uses strategies that are close to optimal (~close to golden ratio e.g. fibonacci, see generics.memoryexpanders)
If fibonacci is chosen it starts at 5, using lookup table for increasing capacity.
Since the next FBN > 3 is the ~ current FBN * 1 GR, where GR = ~1.6180339887, there is an empirically proven optimal trade off between expansion and memory use.
Most of the other strategies there are very close to the above. 1.5 is also a good value. Since its nature a lookup table is both efficient and small < 4GB
Title: Re: Optimize TDeque.IncreaseCapacity
Post by: AlexTP on October 14, 2018, 08:45:49 am
But the code (posted above) does not use Fib numbers at all.
Title: Re: Optimize TDeque.IncreaseCapacity
Post by: Thaddy on October 14, 2018, 09:02:49 am
Yes, but that is from contnrs. I would suggest to adapt the growth factor using one of the tables from generics.memoryexpanders.
Code: Pascal  [Select][+][-]
  1. type
  2.     FBrange = 0..45;
  3. const
  4.   // Fibonacci numbers
  5.   FibonacciNumbers: array[FBrange] of UInt32 = (
  6.     {0,1,1,2,3,}0,5,8,13,21,34,55,89,144,233,377,610,987,
  7.     1597,2584,4181,6765,10946,17711,28657,46368,75025,
  8.     121393,196418,317811,514229,832040,1346269,
  9.     2178309,3524578,5702887,9227465,14930352,24157817,
  10.     39088169, 63245986, 102334155, 165580141, 267914296,
  11.     433494437, 701408733, 1134903170, 1836311903, 2971215073,
  12.     {! not fib number - this is memory limit} 4294967295);
  13.  
  14. // unfinished code, but you get the idea.
  15. // introduce a FCapacityIndex
  16. procedure TDeque.IncreaseCapacity;inline;
  17. var i,OldEnd:SizeUInt;
  18. begin
  19.   OldEnd:=FibonacciNumbers[FCapacityIndex];
  20.   inc(FCapacityIndex);
  21.   SetLength(FData, FibonacciNumbers[FCapacityIndex]);
  22.   if (FStart>0) then
  23.     for i:=0 to FStart-1 do
  24.       FData[OldEnd+i]:=FData[i];
  25. end;
  26.  
Title: Re: Optimize TDeque.IncreaseCapacity
Post by: taazz on October 14, 2018, 10:28:01 am
Quote from: Thaddy on October 14, 2018, 09:02:49 am
Yes, but that is from contnrs. I would suggest to adapt the growth factor using one of the tables from generics.memoryexpanders.
Code: Pascal  [Select][+][-]
  1. type
  2.     FBrange = 0..45;
  3. const
  4.   // Fibonacci numbers
  5.   FibonacciNumbers: array[FBrange] of UInt32 = (
  6.     {0,1,1,2,3,}0,5,8,13,21,34,55,89,144,233,377,610,987,
  7.     1597,2584,4181,6765,10946,17711,28657,46368,75025,
  8.     121393,196418,317811,514229,832040,1346269,
  9.     2178309,3524578,5702887,9227465,14930352,24157817,
  10.     39088169, 63245986, 102334155, 165580141, 267914296,
  11.     433494437, 701408733, 1134903170, 1836311903, 2971215073,
  12.     {! not fib number - this is memory limit} 4294967295);
  13.  
  14. // unfinished code, but you get the idea.
  15. // introduce a FCapacityIndex
  16. procedure TDeque.IncreaseCapacity;inline;
  17. var i,OldEnd:SizeUInt;
  18. begin
  19.   OldEnd:=FibonacciNumbers[FCapacityIndex];
  20.   inc(FCapacityIndex);
  21.   SetLength(FData, FibonacciNumbers[FCapacityIndex]);
  22.   if (FStart>0) then
  23.     for i:=0 to FStart-1 do
  24.       FData[OldEnd+i]:=FData[i];
  25. end;
  26.  
which is as wrong as it can get. It is wastes memory like there is no tomorrow after a specific size dependand on the data the capacity grow should start to getting smaller than the current item count not bigger. This is a stupid man's speed enhancer.
Title: Re: Optimize TDeque.IncreaseCapacity
Post by: Artem3213212 on October 14, 2018, 11:28:56 am
1).
Quote from: Alextp on October 13, 2018, 09:55:33 pm
Code: Pascal  [Select][+][-]
  1. procedure TDeque.IncreaseCapacity;inline;
  2. var i,OldEnd:SizeUInt;
  3. begin
  4.   OldEnd:=FCapacity;
  5.   if(FCapacity=0) then
  6.     FCapacity:=1
  7.   else
  8.     FCapacity:=FCapacity*2;
  9.   SetLength(FData, FCapacity);
  10.   if (FStart>0) then
  11.     for i:=0 to FStart-1 do
  12.       FData[OldEnd+i]:=FData[i];
  13. end;

suggestion: make first value not 1 but cInitialCapacity (const in unit).
Set it not to 1 but to 4, or better 8.

It's correct, but when we work with memory we must understand than when we use more then 1-10 MB RAM we need some slowly asymptotic(it may be Fibonacci numbers).
2) We must understand that:
https://en.wikipedia.org/wiki/Page_(computer_memory)#Multiple_page_sizes
and make FCapacity*sizeof(T) multiple of the page size(4kb/2mb/4mb).
3) I think that we must make possible to use more than 4 GB*sizeof(T) memory in one TDeque => 4294967295 - isn't memory limit.
All of all I think that we must generate array like FibonacciNumbers for each architecture and each sizeof(T).
Title: Re: Optimize TDeque.IncreaseCapacity
Post by: Thaddy on October 14, 2018, 11:41:53 am
Quote from: Artem3213212 on October 14, 2018, 11:28:56 am
3) I think that we must make possible to use more than 4 GB*sizeof(T) memory in one TDeque => 4294967295 - isn't memory limit.
It is, at least it is the memory limit of the default memorymanager for one single entity. It is not the limit of total memory.
As such it would require a specialized memory manager. This is not a limitation of FreePascal perse, you will also find this limitation in most other languages.
BTW there are more options given and available. An alternative would be an approximation using 1.5.
Also note that such a memory manager would not be cross-platform.

We discussed this rather lengthy and backed by theory. Maciej included links to the theory behind the options for reference in generics.memoryexpanders.
Your option is simply not an option.
Title: Re: Optimize TDeque.IncreaseCapacity
Post by: AlexTP on October 14, 2018, 05:13:23 pm
Ok, limit will be 4Gb.
What about other Artem's suggestions?
Title: Re: Optimize TDeque.IncreaseCapacity
Post by: Thaddy on October 14, 2018, 05:27:19 pm
The main suggestion is already implemented by my code snippet....? Initial capacity when used will be 5. Since that has index 1.
Note it depends on use: for small stacks/queues the current implementation is quite satisfactory. That changes with large or huge stack or queues.
(And technically a stack or queue should frankly be of fixed size....anything else is a modernism  O:-) 8-) )

E.g.: a forthlike (Polish notation) calculator - which is stack based - doesn't need a stack over size 256, which is within current implementation efficiency.
But queues for processing real-time data can be over 10's of megabytes in size. Those are much rarer. So it is a trade-off.
(for readers: stacks and queues are similar structures and have much the same behavior except LIFO vs FIFO)
Title: Re: Optimize TDeque.IncreaseCapacity
Post by: AlexTP on October 14, 2018, 06:08:50 pm
But your tip (Fib numbers) is not yet impemented?
https://github.com/graemeg/freepascal/blob/master/packages/fcl-stl/src/gdeque.pp#L141
pls apply it.

Another variant:
>>>TList auto-growth

    Old behaviour: Lists with number of elements greater than 127 was expanded by 1/4 of its current capacity
    New behaviour: Adds two new thresholds. If number of elements is greater than 128 MB then list is expanded by constant amount of 16 MB elements (corresponds to 1/8 of 128 MB). If number of elements is greater then 8 MB then list is expanded by 1/8 of its current capacity.
    Reason for change: Avoid out-of-memory when very large lists are expanded
Title: Re: Optimize TDeque.IncreaseCapacity
Post by: marcov on October 14, 2018, 07:01:38 pm
I'm not sure any form of exponential growth over 2GB is a good thing. I usually use a constant grow size over a certain threshold value.

Empirically that turned out to be a good fit with varied workloads.
Title: Re: Optimize TDeque.IncreaseCapacity
Post by: Thaddy on October 14, 2018, 07:14:14 pm
Quote from: Alextp on October 14, 2018, 06:08:50 pm
But your tip (Fib numbers) is not yet impemented?
https://github.com/graemeg/freepascal/blob/master/packages/fcl-stl/src/gdeque.pp#L141
pls apply it.
I don't need to: Apart from small stacks and queues, I only use generic stacks and queues: there it is implemented very well.
Title: Re: Optimize TDeque.IncreaseCapacity
Post by: Thaddy on October 14, 2018, 07:16:43 pm
Quote from: marcov on October 14, 2018, 07:01:38 pm
Empirically that turned out to be a good fit with varied workloads.
Well, the theory behind it was added. For the general case the current status is perfectly fine. The suggestion is a nano-optimization in that case.
But you seem to agree that powers of two are over-excessive.
Title: Re: Optimize TDeque.IncreaseCapacity
Post by: AlexTP on October 14, 2018, 07:20:40 pm
Can you 'copy' method from "good" Deque to "gdeque.pp" bad deque, to fix my app?
Title: Re: Optimize TDeque.IncreaseCapacity
Post by: AlexTP on October 14, 2018, 07:53:17 pm
What about my change?
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
  23.   else
  24.     FCapacity+=FCapacity div 16;
  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.  
  32.  
Title: Re: Optimize TDeque.IncreaseCapacity
Post by: Thaddy on October 14, 2018, 08:06:38 pm
Quote from: Alextp on October 14, 2018, 07:53:17 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...
Title: Re: Optimize TDeque.IncreaseCapacity
Post by: Artem3213212 on October 14, 2018, 08:45:12 pm
Quote from: Alextp on October 14, 2018, 07:53:17 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.  
Title: Re: Optimize TDeque.IncreaseCapacity
Post by: AlexTP 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]
Title: Re: Optimize TDeque.IncreaseCapacity
Post by: ASerge on October 17, 2018, 09:29:25 pm
I like TFPList.Expand
Title: Re: Optimize TDeque.IncreaseCapacity
Post by: Bart 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 (https://bugs.freepascal.org/view.php?id=38306).

Bart
TinyPortal © 2005-2018