[TCLCORE] Re: Hintermayer's string allocation patch

[Joe E. <jen...@fl...>]

Donald G Porter <dg...@ca...> wrote:
>
> Yes, because (3KB * 1000) compares 2 big reallocs (original algorithm)
> with ~400 small reallocs (new algorithm).  (1KB * 1000) compares only
> 1 big realloc (original algorithm) to ~300 small reallocs.
>
> Results from Tcl 8.4a1:
> 047 {{STR append (1MB + 1KB * 1000)} 61321}
> Results from Tcl in CVS, 2000 August 31:
> 047 {{STR append (1MB + 1KB * 1000)} 68370}
>
> Now, neither test is "the right test".  They're both particular tests,
> but this should dispute the claim that the new patch is faster
> "in all cases".

In addition, since there is only about a ~10% difference
between the two numbers, I strongly suspect that the
"lots of little reallocs" case only does as well as
it does because of the way realloc() happens to be
implemented on the system on which it was run.
IOW: Don's system's realloc() is most likely growing
the allocated memory by powers-of-two internally *anyway*.


> It's worth considering the asymptotics, too.  As others have
> observed, the O(N**2) behavior of the new algorithm will bite when
> the "1000" in these benchmarks grows to 10000, 100000, 1000000, ...

Or on a system with a naive realloc() implementation,
if my guess is correct.


--Joe English

  jen...@fl...

--
The TclCore mailing list is sponsored by Ajuba Solutions
To unsubscribe:  email tcl...@aj... with the 
                 word UNSUBSCRIBE as the subject.