GEMini Atari/GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso/files/gnu/libg_tex/hints

Emacs RMAIL | 1991-11-16 | 19.5 KB | 523 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: <[e-mail]>
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 <[e-mail]>; Sun, 11 Feb 90 21:30:14 -0500
Received: from localhost by raid8.cs.purdue.edu (5.61/PURDUE_CS-1.2)
    id <[e-mail]>; Sun, 11 Feb 90 21:30:08 -0500
Message-Id: <[e-mail]>
To: [e-mail]
Subject: kudos for profiling and libg++
In-Reply-To: Your message of Tue, 09 Jan 90 06:27:17 -0500.
             <[e-mail]>
Date: Sun, 11 Feb 90 21:30:04 EST
From: [e-mail]

*** EOOH ***
Return-Path: <[e-mail]>
To: [e-mail]
Subject: kudos for profiling and libg++
In-Reply-To: Your message of Tue, 09 Jan 90 06:27:17 -0500.
             <[e-mail]>
Date: Sun, 11 Feb 90 21:30:04 EST
From: [e-mail]

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: <[e-mail]>
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: [e-mail] (Doug Lea)
Message-Id: <[e-mail]>
To: [e-mail]
Cc: [e-mail]
In-Reply-To: Jose Cordova's message of Wed, 7 Feb 90 17:28:57 CST <[e-mail]>
Subject: Run-time error when using 'get' with an istream object
Reply-To: [e-mail]

*** EOOH ***
Return-Path: <[e-mail]>
Date: Thu, 8 Feb 90 05:48:50 EST
From: [e-mail] (Doug Lea)
To: [e-mail]
Cc: [e-mail]
In-Reply-To: Jose Cordova's message of Wed, 7 Feb 90 17:28:57 CST <[e-mail]>
Subject: Run-time error when using 'get' with an istream object
Reply-To: [e-mail]


> 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: <[e-mail]>
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 [e-mail]; 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 [e-mail]; Mon, 5 Feb 90 13:06:55 PST
Message-Id: <[e-mail]>
Received: by merlin.aero.org (4.1/SMI-3.2-A4)
    id AA03654 for [e-mail]; Mon, 5 Feb 90 13:06:50 PST
Date: Mon, 5 Feb 90 13:06:50 PST
From: [e-mail]
To: [e-mail]
Subject: Checklist for using Map class

*** EOOH ***
Return-Path: <[e-mail]>
Posted-Date: Mon, 5 Feb 90 13:06:50 PST
Date: Mon, 5 Feb 90 13:06:50 PST
From: [e-mail]
To: [e-mail]
Subject: Checklist for using Map class


I found your last message of Jan 20 was enough to get me
started using the Map class.  I'm attaching some notes
I made in LaTeX format which are intended to get new
users off and running quickly.  It's pretty much in the
form of a checklist that they can just go down and follow.
I was thinking it might be useful to you as a standard
response to inquiries for help from neophytes like myself.

               0          cut here        0
----------------><--------------------------------><------------------
               0                                    0

\documentstyle{article}
\title{Implementing Table Lookup Using the GNU Library}
\begin{document}
\section{Introduction}

This note describes how to use the GNU class library Version 1.35.0
to create lookup tables.
The advantage of using the GNU library is that
the code to implement tables can be quickly generated.
Hopefully, the code is also more reliable than
what we could write ourselves.
In addition, the library provides four different lookup
mechanisms. It is relatively easy to ``switch engines''
and use the fastest one for our application.

This note augments the ``User's Guide to GNU C++ Library''
by filling in some gaps in the manual.
Therefore, it is intended to complement, rather than
replace the original manual.
Section \ref{sec:general} describes the general procedure
for creating a lookup table.
Section \ref{sec:specific} gives a working example, in this
case the creation of a lookup table for database objects.


\section{Using the GNU Library to Create a Lookup Table}
\label{sec:general}

The GNU library provides four implementations of lookup tables:
threaded AVL trees, splay trees, resizable hash tables, and
chained hash tables.
The hash table implementations provide double hashing.
The class names for these implementations are shown below
in Table \ref{tab:imp}.
All four classes are subclasses of the {\tt Map} class. \\
Therefore, to create a lookup table, you must define a table class based
on the abstract class {\tt Map} as well as one of the subclasses.
The script {\tt genclass}, provided
with the GNU library, automates this process.

\begin{table}[htb]
\centering
\caption{\label{tab:imp} GNU Implementations of Lookup Tables}
\begin{tabular}{||l|l||} \hline
{\bf Class Name} & {\bf Implementation Method} \\ \hline
{\tt AVLMap} & Threaded AVL trees. \\
{\tt SplayMap} & Splay trees. \\
{\tt VHMap} & Resizable hash tables. \\
{\tt CHMap} & Chained hash tables. \\ \hline
\end{tabular} \\
\end{table}



A {\sl key} refers to the index for the table
and {\sl base value} refers to the basic data
stored in the table that is returned upon
a keyed lookup.
You need to define a hashing function
and an equality function for the key.
Finally, if you use pointers as your base
value you need to typedef a name for the pointer.
The steps you need to take are shown below.
In these examples, {\tt $<$K$>$} is the name
of the key class,
{\tt $<$B$>$} the name of the class for the base value,
{\tt $<$BP$>$} the name of the type pointer to base value,
and {\tt $<$M$>$} the name of one of the four {\tt Map} subclasses. \\

\begin{tabular}{||r|l|l||} \hline
&&  {\bf Name of } \\
{\bf Step} & {\bf Action} & {\bf Affected File} \\  \hline
1 & Create functions {\tt $<$K$>$HASH} & {\tt $<$K$>$.defs.h} \\
  & and {\tt $<$K$>$EQ}. &{\tt $<$K$>$.defs.cc }  \\ \hline
2 & Define {\tt DEFAULT\_INITIAL\_CAPACITY} & {\tt $<$K$>$.defs.h} \\ \hline
3 & Create typedef {\tt $<$BP$>$}. & {\tt  $<$B$>$.h}  \\
  & for  pointer to base class. & \\ \hline
4 & Create abstract class with  & {\tt $<$K$>$.$<$BP$>$.Map.h}  \\
  & {\tt genclass -2 $<$K$>$ ref $<$BP$>$ val Map}&
  {\tt $<$K$>$.$<$BP$>$.Map.cc} \\ \hline
5 & Edit {\tt $<$K$>$.$<$BP$>$.Map.h} to include &{\tt $<$K$>$.$<$BP$>$.Map.h} \\
  & {\tt $<$K$>$.defs.h} and {\tt  $<$B$>$.h}. &   \\ \hline
6 & Create table class for specific & {\tt $<$K$>$.$<$BP$>$.$<$M$>$.h} \\
  & lookup implementation method with & {\tt $<$K$>$.$<$BP$>$.$<$M$>$.cc} \\
  & {\tt genclass -2 $<$K$>$ ref $<$BP$>$ val $<$M$>$ } & \\ \hline
\end{tabular} \\

The {\tt $<$K$>$} and {\tt $<$BP$>$} arguments to {\tt genclass}
can be qualified by either {\tt val} or {\tt ref} depending on
whether the reference is by value or by reference.

\section{Example: Table Lookup Class for Database Objects}
\label{sec:specific}

In this example, we want to refer to objects from the
user-defined class {\tt Database} by their names so
the name of the database object is the key to the table.
To accommodate the {\tt Map} class need for   hashing on the key,
the name is represented by a {\tt String} and the
hash function is the library {\tt hashpjw} function
declared in {\tt builtin.h}
Thus {\tt $<$K$>$} is {\tt String},
{\tt $<$B$>$} is {\tt Database}, and
{\tt $<$BP$>$} is {\tt Databasep}.
For this example, the lookup mechanism used is resizable
hash tables which have type {\tt VHMap} so
{\tt $<$M$>$} is {\tt VHMap}.

\begin{enumerate}
\item The {\tt Map} classes expect to get
a function called {\tt HStringHASH}
that takes an argument of type {\tt String}
so {\tt hashpjw} was wrapped inside
{\tt HStringHASH}.
Similarly, {\tt HStringEQ} is a wrapper
for the {\tt HString} class operator $=$.
(The $=$ operator is inherited from the {\tt String}
class).
The function headers
for {\tt HStringHASH} and {\tt HStringEQ}
go into {\tt HString.defs.h}
and the function bodies into {\tt HString.defs.cc}.


\item {\tt DEFAULT\_INITIAL\_CAPACITY} was set to {\tt 1021}
in {\tt HString.defs.h}.  You must use the identifier
{\tt DEFAULT\_INITIAL\_CAPACITY} to be consistent with
the {\tt Map} classes.

\item Define {\tt Databasep} as a pointer to class
{\tt Database} in {\tt Database.h}.
An identifier other than {\tt Databasep} would
also be acceptable.  You just can't use {\tt Database*}.

\item {\tt genclass -2 HString ref Databasep val Map} \\
produces {\tt HString.Databasep.Map.h} and \\
{\tt HString.Databasep.Map.cc}.

\item Edit {\tt HString.Databasep.Map.h} to
include {\tt HString.defs.h} and  \\ {\tt Database.h}.

\item {\tt genclass -2 HString ref Databasep val VHMap} \\
produces {\tt HString.Databasep.VHMap.h} and \\
{\tt HString.Databasep.VHMap.cc}.
\end{enumerate}


\end{document}






1,,
Return-Path: <[e-mail]>
Received: from rocky.Oswego.EDU by g.oswego.edu (4.0/SMI-4.0)
    id AA26086; Sat, 3 Feb 90 07:05:17 EST
Received: by oswego.Oswego.EDU (5.57/Osw4.1.19)
    id AA09020; Sat, 3 Feb 90 07:04:44 EST
Received: from life.ai.mit.edu by nisc.nyser.net (5.61/2.1-NYSERNet NISC)
    id AA24615; Sat, 3 Feb 90 07:00:07 -0500
Received: from oswego.Oswego.EDU by life.ai.mit.edu (4.0/AI-4.10) id AA04153; Sat, 3 Feb 90 07:00:15 EST
Received: by oswego.Oswego.EDU (5.57/Osw4.1.19)
    id AA16111; Sat, 3 Feb 90 07:02:52 EST
Received: by g.oswego.edu (4.0/SMI-4.0)
    id AA26081; Sat, 3 Feb 90 07:03:03 EST
Date: Sat, 3 Feb 90 07:03:03 EST
From: [e-mail] (Doug Lea)
Message-Id: <[e-mail]>
To: [e-mail]
Cc: [e-mail]
In-Reply-To: Tom Ngo's message of Fri, 2 Feb 90 23:42:54 EST <[e-mail]>
Subject: Should "operator =" be made to return *this, by convention?
Reply-To: [e-mail]

*** EOOH ***
Return-Path: <[e-mail]>
Date: Sat, 3 Feb 90 07:03:03 EST
From: [e-mail] (Doug Lea)
To: [e-mail]
Cc: [e-mail]
In-Reply-To: Tom Ngo's message of Fri, 2 Feb 90 23:42:54 EST <[e-mail]>
Subject: Should "operator =" be made to return *this, by convention?
Reply-To: [e-mail]


>
>     C programmers are accustomed to expecting = to return the value
>     assigned.  However, in a few classes--for example, String, Integer
>     and Rational-- operator == returns void.  Is there a good reason
>     for this?  Could they be made to return String&, Integer& and
>     Rational& *this without causing problems?
>

The reason that X= (+=, -=, etc.) and = operators return void is to
facilitate simple subclassing. While `utility' classes like String,
Integer, etc., are not designed for extensive subclassing (since no
members are virtual (which, in turn is motivated by efficiency
considerations)), it is often convenient to create simple subclasses
like class Line : public String. If you do this, then it is most
desirable that inherited operators return void.  Otherwise, unexpected
type matches often occur. For example, if operator << (ostream&,
Line&) were redefined for Line, but op += were inherited from String,
and had return value String&, then
    { Line l; ...;  cout << (l += "\n"); }
would invoke op << (ostream&, String&), which is probably not
what anyone would have in mind.  This is avoided by having String::+=
return void, making this usage illegal.

Problems like this outweigh the syntactic convenience of supporting
multiple right-associative uses of X= and =. A good rule of thumb
about all this is that no non-virtual member functions should
ever return *this by reference. (This rule is broken in a few places
in libg++ for various reasons though.)

-Doug


1,,
Return-Path: <[e-mail]>
Received: from rocky.Oswego.EDU by g.oswego.edu (4.0/SMI-4.0)
    id AA00741; Thu, 18 Jan 90 06:01:53 EST
Received: by oswego.Oswego.EDU (5.57/Osw4.1.18)
    id AA22159; Thu, 18 Jan 90 06:02:51 EST
Received: from life.ai.mit.edu by nisc.nyser.net (5.61/2.1-NYSERNet NISC)
    id AA22988; Thu, 18 Jan 90 05:56:52 -0500
Received: from oswego.Oswego.EDU by life.ai.mit.edu (4.0/AI-4.10) id AA00267; Thu, 18 Jan 90 05:58:24 EST
Received: by oswego.Oswego.EDU (5.57/Osw4.1.18)
    id AA16327; Thu, 18 Jan 90 06:01:51 EST
Received: by g.oswego.edu (4.0/SMI-4.0)
    id AA00738; Thu, 18 Jan 90 06:00:57 EST
Date: Thu, 18 Jan 90 06:00:57 EST
From: [e-mail] (Doug Lea)
Message-Id: <[e-mail]>
To: [e-mail]
Cc: [e-mail]
In-Reply-To: Michael Allen's message of Wed, 17 Jan 90 14:56:32 CST <[e-mail]>
Subject: compiling libg++-1.36.3 with g++-1.36.3 on sun4
Reply-To: [e-mail]

*** EOOH ***
Return-Path: <[e-mail]>
Date: Thu, 18 Jan 90 06:00:57 EST
From: [e-mail] (Doug Lea)
To: [e-mail]
Cc: [e-mail]
In-Reply-To: Michael Allen's message of Wed, 17 Jan 90 14:56:32 CST <[e-mail]>
Subject: compiling libg++-1.36.3 with g++-1.36.3 on sun4
Reply-To: [e-mail]



> 2) several files get flagged as a warning that a volatile funtion does
> return, which appears to be false.

Not quite false, but deserving of explanation:

libg++ does not (yet) use the experimental g++ exception handling
facilities (they are still too new: Too many things would have to be
redone if the EH features change). So the only exception strategy is
for error traps like Integer::error() to call the function pointed to
by lib_error_handler (see builtin.h). By default, this points to
default_two_arg_error_handler, which prints a message on stderr and
aborts. But it *can* be reset to do anything at all, and need not
abort execution. On the other hand, *some* (not all) error() member
functions are used in a way that preclude any kind of sensible
continuation even if error() returns. I mark these as `volatile',
since the compiler might as well act as if they cannot return: This is
defensible in that even if (*lib_error_handler) returns, things are
going so wrong that you are no worse off if the compiler generates
(usually faster) code assuming execution aborts.  The compiler
correctly warns about these.

Again, saner strategies will be employed when the C++ exception
handling situation stabilizes.

-Doug



