hints

早期freebsd实现

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}