home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Fresh Fish 7
/
FreshFishVol7.bin
/
bbs
/
gnu
/
libg++-2.6-fsf.lha
/
libg++-2.6
/
libg++
/
etc
/
HINTS
< prev
next >
Wrap
Text File
|
1991-06-28
|
24KB
|
668 lines
BABYL OPTIONS:
Version: 5
Labels:
Note: This is the header of an rmail file.
Note: If you are seeing it in rmail,
Note: it means the file has no messages in it.
1,,
Return-Path: <riedl@cs.purdue.edu>
Received: from oswego.Oswego.EDU by g.oswego.edu (4.0/SMI-4.0)
id AA08377; Sun, 11 Feb 90 21:33:40 EST
Received: by oswego.Oswego.EDU (5.57/Osw4.1.21)
id AA00896; Sun, 11 Feb 90 21:33:18 EST
Received: from raid8.cs.purdue.edu by arthur.cs.purdue.edu (5.61/PURDUE_CS-1.2)
id <AA01233@arthur.cs.purdue.edu>; Sun, 11 Feb 90 21:30:14 -0500
Received: from localhost by raid8.cs.purdue.edu (5.61/PURDUE_CS-1.2)
id <AA19140@raid8.cs.purdue.edu>; Sun, 11 Feb 90 21:30:08 -0500
Message-Id: <9002120230.AA19140@raid8.cs.purdue.edu>
To: dl@oswego.oswego.edu
Subject: kudos for profiling and libg++
In-Reply-To: Your message of Tue, 09 Jan 90 06:27:17 -0500.
<9001091127.AA09544@g.oswego.edu>
Date: Sun, 11 Feb 90 21:30:04 EST
From: riedl@cs.purdue.edu
*** EOOH ***
Return-Path: <riedl@cs.purdue.edu>
To: dl@oswego.oswego.edu
Subject: kudos for profiling and libg++
In-Reply-To: Your message of Tue, 09 Jan 90 06:27:17 -0500.
<9001091127.AA09544@g.oswego.edu>
Date: Sun, 11 Feb 90 21:30:04 EST
From: riedl@cs.purdue.edu
I was having some trouble with the performance of a concurrency
controller I had written, and am very pleased to report that g++
support for profiling, and the excellent libg++ data structure support
saved the day! I include a detailed description of the problem and
solution below, which you are welcome to send to any of the involved
parties for encouragement, or to publish for bragging rights (:-).
Nice job!
John
------
The basic problem was that two concurrency controllers that I had
written, called T/O and Lock for short, should have had similar
performance characteristics, but didn't. After some days of work it
became clear that T/O was significantly slower than Lock, for reasons
that I couldn't understand. I profiled the two routines and found the
profiles to be very similar, as expected, with the exception of a
large number of calls to compare_item in T/O:
calls to compare_item total time
T/O 118,112 0.43 10.76 seconds
LOCK 6601*[2-3] 0.09 seconds 9.02 seconds
(The numbers involved are small because I did the run for 100
transactions. Real runs will be for several orders of magnitude more
transactions.)
(I don't have an exact number for the number of calls to compare item
for Lock for obscure reasons, but my understanding of the program
makes me confident that it was called 2-3 times for each call to its
parent, which was called 6601 times.)
The additional 1.74 seconds spent in T/O could almost all be accounted
for by calls to compare_item and its parent, SLSet::seek. Since the
data structures involved were relatively small I expected that using a
fancier data structure wouldn't help, but I thought I should test the
potential. I determined that the data structures involved would grow
to about 300 items, and that items would be accessed much more often
than they would be inserted. So I timed versions using the linked
list and using AVL trees:
program items accesses seconds (user time)
sl-set 300 10,000 7.70
sl-set 300 10,000 7.61
sl-set 3000 10,000 91.35
avl-set 300 1,000 0.18
avl-set 300 10,000 0.68
avl-set 300 100,000 6.15
avl-set 3000 10,000 1.48
Clearly the AVL tree implementation was far superior, even for small
problem sizes. I installed the AVL sets in T/O and they solved the
performance problem I was having. Profiling shows that before the
change:
calls to compare_item total time
T/O 118,112 0.43 10.76 seconds
LOCK 6601*[2-3] 0.09 seconds 9.02 seconds
After the change locking is the same, but:
T/O 16,048 0.10 seconds 9.08 seconds
The lessons I take from this study are:
1) Linked lists may cause performance problems even if the lists are
relatively short (< 100 items) if they are heavily used.
2) The C++ library can be extremely advantageous. In this case, I
made a two line change to my program to change to AVL trees.
3) Profiling is essential to understanding program performance.
John Riedl
1,,
Return-Path: <dl@g.oswego.edu>
Received: from rocky.Oswego.EDU by g.oswego.edu (4.0/SMI-4.0)
id AA03598; Thu, 8 Feb 90 05:50:05 EST
Received: by oswego.Oswego.EDU (5.57/Osw4.1.21)
id AA08592; Thu, 8 Feb 90 05:47:12 EST
Received: from life.ai.mit.edu by nisc.nyser.net (5.61/2.1-NYSERNet NISC)
id AA07649; Thu, 8 Feb 90 05:44:40 -0500
Received: from oswego.Oswego.EDU by life.ai.mit.edu (4.0/AI-4.10) id AA29896; Thu, 8 Feb 90 05:46:04 EST
Received: by oswego.Oswego.EDU (5.57/Osw4.1.21)
id AA27161; Thu, 8 Feb 90 05:48:41 EST
Received: by g.oswego.edu (4.0/SMI-4.0)
id AA03595; Thu, 8 Feb 90 05:48:50 EST
Date: Thu, 8 Feb 90 05:48:50 EST
From: dl@g.oswego.edu (Doug Lea)
Message-Id: <9002081048.AA03595@g.oswego.edu>
To: jose@csserver.cs.msstate.edu
Cc: bug-lib-g++@prep.ai.mit.edu
In-Reply-To: Jose Cordova's message of Wed, 7 Feb 90 17:28:57 CST <9002072328.AA07167@CSServer.CS.MsState.Edu>
Subject: Run-time error when using 'get' with an istream object
Reply-To: dl@oswego.oswego.edu
*** EOOH ***
Return-Path: <dl@g.oswego.edu>
Date: Thu, 8 Feb 90 05:48:50 EST
From: dl@g.oswego.edu (Doug Lea)
To: jose@csserver.cs.msstate.edu
Cc: bug-lib-g++@prep.ai.mit.edu
In-Reply-To: Jose Cordova's message of Wed, 7 Feb 90 17:28:57 CST <9002072328.AA07167@CSServer.CS.MsState.Edu>
Subject: Run-time error when using 'get' with an istream object
Reply-To: dl@oswego.oswego.edu
> I am having trouble using the 'get' method for the 'istream' class.
> It generates a 'Segmentation fault' error at run-time. I know the
> 'istream' is being opened correctly because reading into a 'String'
> object with >> works fine. Am I doing something wrong ?
> The sample program and "data" illustrate the point:
>
> main()
> {
> istream from("data",io_readonly,a_useonly);
> char *line;
>
> from.get(line,15);
> cout << line;
> }
>
> Sample "data" file contents:
> word1 word2
> word3
>
There are 3 istream functions for reading char*'s
istream& get (char* s, int n, char terminator = '\n');
istream& getline(char* s, int n, char terminator = '\n');
istream& gets (char **s, char terminator = '\n');
The first two *require* an allocated char* (they differ only
in how the trailing terminator is handled.) To use them, you
must supply either a char[N] or an allocated char*.
The third automatically allocates space for you, that you should
later delete.
For example,
main()
{
istream from("data",io_readonly,a_useonly);
char *line = new char[16]; // enough for string + null
char line2[16];
char* line3 = 0; // `= 0' so delete'able even if never allocated --
// Not necessary in this example.
from.get(line,15);
from.get(line2,15);
from.gets(&line3,15); // pass in the addr of line3
cout << line;
cout << line2;
cout << line3;
delete line;
delete line3;
}
Using the String class is a very good way to avoid dealing with these
kinds of char* allocation and semantics issues.
-Doug
1, answered,,
Return-Path: <chowkwan@aerospace.aero.org>
Received: from aerospace.aero.org ([130.221.192.10]) by g.oswego.edu (4.0/SMI-4.0)
id AA03846; Mon, 5 Feb 90 16:10:27 EST
Received: from antares.aero.org by aerospace.aero.org with SMTP (5.61++/6.0.GT)
id AA24377 for dl@g.oswego.edu; Mon, 5 Feb 90 13:06:58 -0800
Posted-Date: Mon, 5 Feb 90 13:06:50 PST
Received: from merlin.aero.org by antares.aero.org (4.1/SMI-3.2-A4ant)
id AA20056 for dl@g.oswego.edu; Mon, 5 Feb 90 13:06:55 PST
Message-Id: <9002052106.AA20056@antares.aero.org>
Received: by merlin.aero.org (4.1/SMI-3.2-A4)
id AA03654 for dl@g.oswego.edu; Mon, 5 Feb 90 13:06:50 PST
Date: Mon, 5 Feb 90 13:06:50 PST
From: chowkwan@aerospace.aero.org
To: dl@g.oswego.edu
Subject: Checklist for using Map class
*** EOOH ***
Return-Path: <chowkwan@aerospace.aero.org>
Posted-Date: Mon, 5 Feb 90 13:06:50 PST
Date: Mon, 5 Feb 90 13:06:50 PST
From: chowkwan@aerospace.aero.o