Recent

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

AlexTP

  • Hero Member
  • *****
  • Posts: 2386
    • UVviewsoft
Optimize TDeque.IncreaseCapacity
« 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.
« Last Edit: October 13, 2018, 09:57:05 pm by Alextp »

Thaddy

  • Hero Member
  • *****
  • Posts: 14204
  • Probably until I exterminate Putin.
Re: Optimize TDeque.IncreaseCapacity
« Reply #1 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
« Last Edit: October 14, 2018, 08:54:21 am by Thaddy »
Specialize a type, not a var.

AlexTP

  • Hero Member
  • *****
  • Posts: 2386
    • UVviewsoft
Re: Optimize TDeque.IncreaseCapacity
« Reply #2 on: October 14, 2018, 08:45:49 am »
But the code (posted above) does not use Fib numbers at all.

Thaddy

  • Hero Member
  • *****
  • Posts: 14204
  • Probably until I exterminate Putin.
Re: Optimize TDeque.IncreaseCapacity
« Reply #3 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.  
« Last Edit: October 14, 2018, 09:09:45 am by Thaddy »
Specialize a type, not a var.

taazz

  • Hero Member
  • *****
  • Posts: 5368
Re: Optimize TDeque.IncreaseCapacity
« Reply #4 on: October 14, 2018, 10:28:01 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.
Good judgement is the result of experience … Experience is the result of bad judgement.

OS : Windows 7 64 bit
Laz: Lazarus 1.4.4 FPC 2.6.4 i386-win32-win32/win64

Artem3213212

  • New member
  • *
  • Posts: 7
Re: Optimize TDeque.IncreaseCapacity
« Reply #5 on: October 14, 2018, 11:28:56 am »
1).
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).

Thaddy

  • Hero Member
  • *****
  • Posts: 14204
  • Probably until I exterminate Putin.
Re: Optimize TDeque.IncreaseCapacity
« Reply #6 on: October 14, 2018, 11:41:53 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.
« Last Edit: October 14, 2018, 11:58:34 am by Thaddy »
Specialize a type, not a var.

AlexTP

  • Hero Member
  • *****
  • Posts: 2386
    • UVviewsoft
Re: Optimize TDeque.IncreaseCapacity
« Reply #7 on: October 14, 2018, 05:13:23 pm »
Ok, limit will be 4Gb.
What about other Artem's suggestions?

Thaddy

  • Hero Member
  • *****
  • Posts: 14204
  • Probably until I exterminate Putin.
Re: Optimize TDeque.IncreaseCapacity
« Reply #8 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)
« Last Edit: October 14, 2018, 05:40:13 pm by Thaddy »
Specialize a type, not a var.

AlexTP

  • Hero Member
  • *****
  • Posts: 2386
    • UVviewsoft
Re: Optimize TDeque.IncreaseCapacity
« Reply #9 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

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11383
  • FPC developer.
Re: Optimize TDeque.IncreaseCapacity
« Reply #10 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.

Thaddy

  • Hero Member
  • *****
  • Posts: 14204
  • Probably until I exterminate Putin.
Re: Optimize TDeque.IncreaseCapacity
« Reply #11 on: October 14, 2018, 07:14:14 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.
Specialize a type, not a var.

Thaddy

  • Hero Member
  • *****
  • Posts: 14204
  • Probably until I exterminate Putin.
Re: Optimize TDeque.IncreaseCapacity
« Reply #12 on: October 14, 2018, 07:16:43 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.
Specialize a type, not a var.

AlexTP

  • Hero Member
  • *****
  • Posts: 2386
    • UVviewsoft
Re: Optimize TDeque.IncreaseCapacity
« Reply #13 on: October 14, 2018, 07:20:40 pm »
Can you 'copy' method from "good" Deque to "gdeque.pp" bad deque, to fix my app?

AlexTP

  • Hero Member
  • *****
  • Posts: 2386
    • UVviewsoft
Re: Optimize TDeque.IncreaseCapacity
« Reply #14 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.  

 

TinyPortal © 2005-2018