X-Authentication-Warning: delorie.com: mailnull set sender to djgpp-bounces using -f Message-ID: <3C655E12.6F8D351E@yahoo.com> From: CBFalconer Organization: Ched Research X-Mailer: Mozilla 4.75 [en] (Win98; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.os.msdos.djgpp Subject: Re: Alignment problem References: <3c63f21f DOT sandmann AT clio DOT rice DOT edu> <3C645F1D DOT C26E8F64 AT yahoo DOT com> <3c64b7cf DOT sandmann AT clio DOT rice DOT edu> <3C650C18 DOT B45F67D4 AT yahoo DOT com> <4331-Sat09Feb2002145741+0200-eliz AT is DOT elta DOT co DOT il> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 137 Date: Sat, 09 Feb 2002 18:14:21 GMT NNTP-Posting-Host: 12.90.168.198 X-Complaints-To: abuse AT worldnet DOT att DOT net X-Trace: bgtnsc05-news.ops.worldnet.att.net 1013278461 12.90.168.198 (Sat, 09 Feb 2002 18:14:21 GMT) NNTP-Posting-Date: Sat, 09 Feb 2002 18:14:21 GMT To: djgpp AT delorie DOT com DJ-Gateway: from newsgroup comp.os.msdos.djgpp Reply-To: djgpp AT delorie DOT com Eli Zaretskii wrote: > > > From: CBFalconer > > 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 -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)