I had the thought that the extreme bais for the first run I demonstrated above (with large numbers of smallish allocations going on), might be due to the first run having 'virgin' heap to allocate from?

On second and subsequent runs, the heap has a long chain of free blocks that have to be traversed and/or coallesed when allocating the memory.

That seems to be born out by the fact that the bias reduces markedly with each extra iteration the first test completes.

Am I venting hot air again?

I don't see that on FreeBSD.

Win32's malloc() is particularly stupid that way. You trigger this problem in spades by allocating a bunch of identically-sized buffers that are larger than the typical allocation size and repeatedly freeing them then waiting then reallocating them.

Win32's malloc() gets this case so amazingly wrong that it isn't even funny anymore. When you free the buffers, it leaves a bunch of fixed-size holes in the heap. Then, as tiny things get allocated, it takes a tiny chunk out of each hole (so broken it doesn't even take a bunch of tiny chunks out of the first hole before moving on to the second).

Build a Perl that uses Perl's malloc and you'll likely not see this problem either.

- tye        

I don't suppose that you are still familiar with the Win32 makefile enough to tell me where I should enable USE_PERL_MALLOC?

Update: I worked it out. As well as uncommenting PERL_MALLOC near the top which I had tried without effect, you also have to comment out USE_IMP_SYS. (Which I was reluctant to do becasue then I loose fork. )

However, the reult of doing that is:

        cl -c -I.. -nologo -Gf -W3 -I..\lib\CORE -I.\include -I. -I.. 
+-DWIN32 -D_CONSOLE -DNO_STRICT -DHAVE_DES_FCRYPT -DPERLDLL -DPERL_COR
+E   -MD -Zi -DNDEBUG -O1  -DPERL_IMPLICIT_CONTEXT -DUSE_PERLIO -DPERL
+_MSVCRT_READFIX -Fo..\malloc.obj ..\malloc.c
cl : Command line warning D4029 : optimization is not available in the
+ standard edition compiler
malloc.c
..\malloc.c(1173) : warning C4013: 'malloced_size' undefined; assuming
+ extern returning int
..\malloc.c(1222) : warning C4018: '<' : signed/unsigned mismatch
..\malloc.c(1224) : error C2065: 'PL_malloc_mutex' : undeclared identi
+fier
..\malloc.c(1224) : warning C4133: 'function' : incompatible types - f
+rom 'int *' to 'LPCRITICAL_SECTION'
..\malloc.c(1229) : warning C4018: '>=' : signed/unsigned mismatch
..\malloc.c(1269) : warning C4133: 'function' : incompatible types - f
+rom 'int *' to 'LPCRITICAL_SECTION'
..\malloc.c(1451) : warning C4133: 'function' : incompatible types - f
+rom 'int *' to 'LPCRITICAL_SECTION'
..\malloc.c(1459) : warning C4133: 'function' : incompatible types - f
+rom 'int *' to 'LPCRITICAL_SECTION'
..\malloc.c(1518) : warning C4133: 'function' : incompatible types - f
+rom 'int *' to 'LPCRITICAL_SECTION'
..\malloc.c(1669) : warning C4018: '<' : signed/unsigned mismatch
..\malloc.c(1671) : warning C4018: '<' : signed/unsigned mismatch
..\malloc.c(1743) : warning C4133: 'function' : incompatible types - f
+rom 'int *' to 'LPCRITICAL_SECTION'
..\malloc.c(1904) : warning C4133: 'function' : incompatible types - f
+rom 'int *' to 'LPCRITICAL_SECTION'
..\malloc.c(2085) : warning C4133: 'function' : incompatible types - f
+rom 'int *' to 'LPCRITICAL_SECTION'
..\malloc.c(2088) : warning C4133: 'function' : incompatible types - f
+rom 'int *' to 'LPCRITICAL_SECTION'
..\malloc.c(2267) : warning C4133: 'function' : incompatible types - f
+rom 'int *' to 'LPCRITICAL_SECTION'
..\malloc.c(2275) : warning C4133: 'function' : incompatible types - f
+rom 'int *' to 'LPCRITICAL_SECTION'
..\malloc.c(2278) : warning C4133: 'function' : incompatible types - f
+rom 'int *' to 'LPCRITICAL_SECTION'
..\malloc.c(2384) : warning C4133: 'function' : incompatible types - f
+rom 'int *' to 'LPCRITICAL_SECTION'
..\malloc.c(2410) : warning C4133: 'function' : incompatible types - f
+rom 'int *' to 'LPCRITICAL_SECTION'
..\malloc.c(2441) : warning C4013: 'get_mstats' undefined; assuming ex
+tern returning int
NMAKE : fatal error U1077: 'cl' : return code '0x2'
Stop.
[download]

:(

</Update>

As you can see below, I added _DUSE_PERL_MALLOC (and -DUSE_HASH_SEED_EXPLICIT) to the ccflags in the makefile, rebuilt and saw no change (to either option). The first iteration of the lexically first test (in my benchmark above) still runs nearly 800% qucker than any subsequent pass, and the hash key iterators are not being randomised.

The defines are passed on the command line as the makefile runs, and they are listed in the -V output (near the top), but Tracing through with the debugger and I am still ending up in the MSVCRT when perlsafesysmalloc() is called.

Lower down the -V output it lists "Compile time options" and neither of the two I added show up there?

Any thoughts?

P:\src\perl-5.8.4\win32>..\perl -V
Summary of my perl5 (revision 5 version 8 subversion 4) configuration:
  Platform:
    osname=MSWin32, osvers=4.0, archname=MSWin32-x86-multi-thread
    uname=''
    config_args='undef'
    hint=recommended, useposix=true, d_sigaction=undef
    usethreads=undef use5005threads=undef useithreads=define 
    usemultiplicity=define useperlio=define d_sfio=undef 
    uselargefiles=define usesocks=undef use64bitint=undef 
    use64bitall=undef uselongdouble=undef
    usemymalloc=n, bincompat5005=undef
  Compiler:
    cc='cl', ccflags ='-nologo -Gf -W3 -MD -Zi -DNDEBUG -O1 -DWIN32 -D
+_CONSOLE 
    -DNO_STRICT -DHAVE_DES_FCRYPT -DUSE_HASH_SEED_EXPLICIT -DUSE_PERL_
+MALLOC  
    -DPERL_IMPLICIT_CONTEXT -DPERL_IMPLICIT_SYS -DUSE_PERLIO -DPERL_MS
+VCRT_READFIX',
    optimize='-MD -Zi -DNDEBUG -O1',
    cppflags='-DWIN32'
    ccversion='', gccversion='', gccosandvers=''
    intsize=4, longsize=4, ptrsize=4, doublesize=8, byteorder=1234
    d_longlong=undef, longlongsize=8, d_longdbl=define, longdblsize=10
    ivtype='long', ivsize=4, nvtype='double', nvsize=8, Off_t='__int64
+', lseeksize=8
    alignbytes=8, prototype=define
  Linker and Libraries:
    ld='link', ldflags ='-nologo -nodefaultlib -debug -opt:ref,icf  
        -libpath:"c:\perl584\lib\CORE"  -machine:x86'
    libpth=c:\cl\lib
    libs=  oldnames.lib kernel32.lib user32.lib gdi32.lib winspool.lib
+  comdlg32.lib 
    advapi32.lib shell32.lib ole32.lib oleaut32.lib  netapi32.lib uuid
+.lib wsock32.lib 
    mpr.lib winmm.lib  version.lib odbc32.lib odbccp32.lib msvcrt.lib
    perllibs=  oldnames.lib kernel32.lib user32.lib gdi32.lib winspool
+.lib  comdlg32.lib 
    advapi32.lib shell32.lib ole32.lib oleaut32.lib  netapi32.lib uuid
+.lib wsock32.lib 
    mpr.lib winmm.lib  version.lib odbc32.lib odbccp32.lib msvcrt.lib
    libc=msvcrt.lib, so=dll, useshrplib=yes, libperl=perl58.lib
    gnulibc_version='undef'
  Dynamic Linking:
    dlsrc=dl_win32.xs, dlext=dll, d_dlsymun=undef, ccdlflags=' '
    cccdlflags=' ', lddlflags='-dll -nologo -nodefaultlib -debug -opt:
+ref,icf  
    -libpath:"c:\perl584\lib\CORE"  -machine:x86'


Characteristics of this binary (from libperl):
  Compile-time options: MULTIPLICITY USE_ITHREADS USE_LARGE_FILES 
      PERL_IMPLICIT_CONTEXT PERL_IMPLICIT_SYS
  Built under MSWin32
  Compiled at Jul 13 2004 08:21:31
  %ENV:
    PERL_HASH_SEED="1"
  @INC:
    P:/src/perl-5.8.4/lib
    .
[download]

---

Examine what is said, not who speaks.

"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
"Memory, processor, disk in that order on the hardware side. Algorithm, algoritm, algorithm on the code side." - tachyon