Mail Archives: djgpp/2002/02/09/13:15:21
Eli Zaretskii wrote:
>
> > From: CBFalconer <cbfalconer AT yahoo DOT com>
> > Newsgroups: comp.os.msdos.djgpp
> > Date: Sat, 09 Feb 2002 12:07:01 GMT
> > >
> > > A patch to the code would be preferred; or at least a profiling of
> > > the behavior to identify the locations where the time is spent.
> > > It sounds like some nasty o(n**2) or o(n**3) algorithm issue.
> > >
> > > Everyone on the development team has a long list of things they
> > > are working on - so unless someone adopts the problem or someone
> > > provides a patch, it's likely to remain slow.
> >
> > I scanned quickly through djlsr203.zip without seeing anything
> > meaningful to me. I am not in the least familiar with the
> > runtime.
>
> The source of malloc and free is in the library on file
> src/libc/ansi/stdlib/malloc.c. To begin investigating the slowness,
> I'd suggest to copy that file into some directory, build a program
> with -pg, and then run it and look at the profile. The program in
> which you saw the slow free operation sounds like a good testbed for
> this. The tricky part is to find a program whose run time is
> dominated by the malloc/free code, and make sure the run time is at
> least several seconds, so that the 54-msec granularity of the DOS
> clock doesn't matter.
Those sources ARE in djlsr203.zip, I assume. No problem getting
the time up there - see paste below. I assume this can be done
without recompiling the run-time? I don't want to disturb a
system that is working well when I don't know my way around it -
thus no upgrade of gcc (2.953), which would foul at least gpc.
As I said before, the problem is not unique to DJGPP. A fix for
this might well impact other attributes which are usually more
important. I can well imaging that the cure could be to simply
mark areas free and join them only to immediately adjacent free
areas, leaving any further compaction to malloc only when and if
needed. I assume that malloc/free work on some master pool until
more is needed.
What I did notice was that a simple malloc was compiled in-line in
at least one case, and by a call in another (in the same
program). So there is some intimate knowledge of the malloc
algorithm built into the compiler, possibly via the headers. This
gives me grave doubts as to the easiness and independence of any
fix. It also means that any change would invalidate all sorts of
object files without creating obvious errors. Brrrr.
=========================================
Example of elapsed times, running an O(N) algorithm. Odd values
only suppress the frees at termination time. At these sizes the
runtime (outside of free) is dominated by loading time. For the
first free is gobbling about 0.9 sec, for the second about 5.5
sec. The equivalent threshold under VC6 is around 50 to 100,000
items. These are with a 486DX/80.
=========================================
[1] c:\c\hashlib>timerun hashtest 4 10000
Timer 3 on: 11:56:40
HASHLIB test04
New table, inserting 10000 values
Status: Entries=10000, Deleted=0, Probes=48310, Misses=24413
Walking returned 0
0 items were inserted 0 times
10000 items were inserted 1 times
...
Timer 3 off: 11:56:43 Elapsed: 0:00:02.53
[1] c:\c\hashlib>timerun hashtest 4 10001
Timer 3 on: 11:56:48
HASHLIB test04
New table, inserting 10001 values
Status: Entries=10001, Deleted=0, Probes=48311, Misses=24413
Walking returned 0
0 items were inserted 0 times
10001 items were inserted 1 times
...
Suppressing hshkill()
Timer 3 off: 11:56:49 Elapsed: 0:00:01.59
[1] c:\c\hashlib>timerun hashtest 4 20000
Timer 3 on: 12:01:18
HASHLIB test04
New table, inserting 20000 values
Status: Entries=20000, Deleted=0, Probes=98309, Misses=50115
Walking returned 0
0 items were inserted 0 times
20000 items were inserted 1 times
...
Timer 3 off: 12:01:26 Elapsed: 0:00:07.36
[1] c:\c\hashlib>timerun hashtest 4 20001
Timer 3 on: 12:01:34
HASHLIB test04
New table, inserting 20001 values
Status: Entries=20001, Deleted=0, Probes=98311, Misses=50116
Walking returned 0
0 items were inserted 0 times
20001 items were inserted 1 times
...
Suppressing hshkill()
Timer 3 off: 12:01:36 Elapsed: 0:00:01.87
FYI, the following are the DJGPP things presently installed:
> [1] c:\c\hashlib>sd \djgpp\zipsused /4/r-
> -----------------------------------------------------------------------------
> -oldvers <Dir>-cdecl25s.zip 25719-flx254b .zip 192k-gpp2953b.zip 1760k-
> -descript.ion 646-dif272b .zip 288k-gcc2953b.zip 1952k-gwk306b .zip 544k-
> -bnu2112b.zip 2656k-djdev203.zip 1504k-gdb500b .zip 1120k-mak3791b.zip 288k-
> -bsh204b .zip 448k-faq230b .zip 672k-gmp401b .zip 576k-rh1478b .zip 2048k-
> -bsn129b .zip 800k-fil40b .zip 1344k-gpc2953b.zip 2016k-txi40b .zip 640k-
> -cdecl25b.zip 128k-..................-..................-..................-
> -----------------------------------------------------------------------------
> Path: C:\DJGPP\ZIPSUSED
--
Chuck F (cbfalconer AT yahoo DOT com) (cbfalconer AT XXXXworldnet DOT att DOT net)
Available for consulting/temporary embedded and systems.
(Remove "XXXX" from reply address. yahoo works unmodified)
mailto:uce AT ftc DOT gov (for spambots to harvest)
- Raw text -