delorie.com/archives/browse.cgi   search  
Mail Archives: djgpp/1992/09/30/12:55:41

From: huebner AT usakov DOT gmd DOT de (Uwe Huebner)
Subject: Re: debug32 (fwd)
To: djgpp AT sun DOT soe DOT clarkson DOT edu
Date: Wed, 30 Sep 92 16:58:59 MET DST

Forwarded message:

>From huebner Wed Sep 30 16:56:51 1992
Subject: Re: debug32
To: "Thomas J. Merritt" <tjm AT netcom DOT com>
Date: Wed, 30 Sep 92 16:56:51 MET DST
In-Reply-To: <9209292327 DOT AA00425 AT netcom DOT com>; from "Thomas J. Merritt" at Sep 29, 92 4:28 pm
X-Mailer: ELM [version 2.2 PL10]

TJ Merritt wrote:
> 
> |<><><><><> Original message from dj AT athena DOT ctron DOT com  <><><><><>
> |>1. Why does debug32 take such a long time to load a program?  With a
> |>program size of 700-800K it takes many MINUTES to load which is
> |>tiresome as it usually only takes a second from then to run hte
> |>program, crash and say "where".
> |
> |Because it loads all the symbols at startup.  I don't like it either,
> |but there isn't an easy way to fix it AND not run out of code space in
> |debug32.
> 
> Actually the problem is only partially that all of the symbol get
> read at startup.  The real problem is that symbols are kept in a
> binary tree.  This is not such a problem except that symbols tend
> to be in relatively sorted order and the tree degenerates to nearly
> a linked list.  The symbol insertion time is O(n^2).  Keeping the
> symbols in a hash table would reduce insertion time to O(n) and
> make loading of large files bearable.

Hashing only reduces the effort by a constant!

> 
> Converting debug32 from binary trees to hash tables would not be all that
> difficult.  Unfortunately I haven't had the time to do this.  (Nor
> the inclination since I'm still using djgpp 1.05 for various reasons)
> If anyone would like to tackle this change I would certainly be willing
> to help.
> 

Consider to take an AVL-tree! The insertion time is O(log n) and
the tree cannot degenerate!

If you _really_ needed one, I would provide one!

Greetings

Uwe
-- 
-------------------------------------------------------------------
Uwe Huebner                          e-mail: huebner AT borneo DOT gmd DOT de
GMD/SET
P.O.Box 1316                             Phone: (+49) 2241 14-2771
D-5205 Sankt Augustin 1                    Fax: (+49) 2241 14-2342
-------------------------------------------------------------------

- Raw text -


  webmaster     delorie software   privacy  
  Copyright © 2019   by DJ Delorie     Updated Jul 2019