synopse / mORMot

Synopse mORMot 1 ORM/SOA/MVC framework - Please upgrade to mORMot 2 !
https://synopse.info
788 stars 325 forks source link

Update SynCrossPlatformJSON.pas #402

Closed vlyak closed 3 years ago

vlyak commented 3 years ago

in "AddNameValue" change memory allocation as intended. Old realization always realocate memory to count+(count/8)+32

synopse commented 3 years ago

It is as intended indeed.

The shr 3 is on purpose, to avoid reallocations when the number becomes big. It makes a huge performance difference.

vlyak commented 3 years ago
  1. VCount<=length(Values) always true, because VCount < VCount+...+32. -> VCount >= length(Values) ( in case first allocation Values Length(Values) == 0 and VCount == 0)
  2. dinamically wide reallocation must be look like as SetLength(Values,*VCount+((VCount+8) shr 3) 32) or SetLength(Values,VCount+(VCount shl** 3)+32). Easy way realocate array for 32 nodes: SetLength(Values,VCount+32)
synopse commented 3 years ago
  1. <= is indeed wrong. But since VCount is always increasing by 1, = comparison would be fine enough.
  2. This is not true in practice. SHL 3 is pretty wrong for sure, and will allocate 8 times too much memory.
vlyak commented 3 years ago

Condition >= is more strong than =

Consider the procedure SetLength(VCount+VCount shl 3+32) work for 1M array: 1 call: if 0 >= 0 then reallocate 0 + 0 8 + 32 = 32 elements. 2 call: if 1 >= 32 then do noting ... 32 call: reallocate 32 + 328 + 32 = 320 elements ... 320 call: reallocate 2912 elements ... 2912 -> 26240 -> 236192 -> 2125570 total 7 reallocations, less memory fragmentation, but last allocate 2 times more memory than necessary, but reallocate 236K. It is better to use the following expression: VCount+32: allocate times is (Size div 32) (or Size shr 5). Or not 32 but 64 or 128... Or simple geometrical progression NewSize := OldSize 1.6 (the golden ratio): VCount + 32 + Round(VCount 0.61) or VCount + 32 + Round(VCount * 0.39)

synopse commented 3 years ago

This is a well known suggest, tested since years on multiple part of the algorithm literature (e.g. Knuth). SHL 3 is pretty wrong, because it allocates way too much unused memory, SHR 3 is good enough for a simple implementation. A good and proven balance is what we use in our main framework: https://github.com/synopse/mORMot2/blob/master/src/core/mormot.core.base.pas#L4262