970917 C++ optimization eats all memory on i386 Linux

[Derek Upham]

At the end of this message is a C++ program that implements an anagram
generator.  The program is the complete version of the anagram loader
provided in my 970916 bug report.  The command line to run the program
is once again:

    ./badtest 'My Basis String' < /usr/dict/words

If the code is compiled without optimization, it works perfectly.
However, if the code is compiled with the optimization flag "-O", it
consumes all available memory (roughly 40MB, on a 64MB machine) and
exits with the message "virtual memory exhausted".  It is unclear
whether the compiler would eventually reach an upper bound on its
memory usage, but the small size of the code suggests that this is
runaway memory consumption.

My environment has the following particulars:

System: i586-pc-linux-gnu, Linux 2.0.30
Compiler: cc1plus, EGCS snapshot 970917
Binutils: version 2.8.1
C Library: glibc-2.0.5c
C++ Library: libstdc++ snapshot 970917


Derek

-- 
Derek Upham
sand@celia.serv.net                                 http://www.serv.net/~sand

"Ha!  Your Leaping Tiger Kung Fu is no match for my Frightened Piglet style!"

--------------------------------- cut here ----------------------------------
//
// BADTEST.CC
//

#include <algorithm>
#include <clocale>
#include <cstdlib>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <string>
#include <vector>

/*

Look for collections of words whose letters, when combined, exactly
match the letters in a given string.  "Derek Lynn Upham", the
motivating example, is exactly matched by "naked nymph lure" and
"drunk hymen plea".



The program expects a dictionary of words to be available on
stdin.  This dictionary should be in the form

     word1
     word2
     word3
     ...

with the words separated by whitespace and containing no whitespace
themselves.  "/usr/dict/words" is typically a valid dictionary.



The program depends on the concept of `canonical form'.  Given a word
"w" formed of printable characters, there is a subset of those
characters that test positive with the "isalpha()" function.  To
generate the canonical form of the word, extract the characters in
that subset, downcase the subset, and sort the subset into
lexicographical order.

        In theory, this system could work for locales other than the
        "C" locale.  The "isalpha()" and "tolower()" functions are
        locale-dependent, and we can use the "strxfrm()" function to
        convert the strings into arrays of collation tokens before
        doing the sort (I think).  Unfortunately, tests show that GNU
        libc 2.0.5 doesn't sort the Spanish characters "ch" and "ll"
        in the "es_ES" locale, which doesn't bode well.

The general technique is for doing the search is to take a string
argument and convert it to canonical form, calling it the test string.
Iterate through a dictionary of words looking for candidates that are
proper subsets of the test string.  When we find a candidate, we save
it, extract its characters from the test string, and perform a
recursive search on the dictionary for the reduced test string.  If
the reduced test string ever becomes empty, then we have found an
exact match and can print out all the accumulated candidates.



The program uses several tricks to reduce the size of the test space,
which is the most effective means of improving performance.

1. When the program loads the dictionary from stdin, it checks whether
each word is a subset of the original test string.  This allows us to
ignore words that have no chance of ever being an anagram word.  For
example, the test string "begin" (whose canonical form is also
"begin") is a superset of words "beg" and "gin", so these are added to
the dictionary; it is not a superset of "end" (canonical form "den"),
so "end" is not added.

2. We can partition the dictionary into groups, based on the first
character of the canonical form.  Thus, all words with an "a" or "A"
in them are in group "a", while all words with no "a" or "A", but with
"b" or "B" are in group "b".  The *only* group we need to traverse
during a given search is the one that matches the first character of
the test string.  Consider the test string "begin": we can ignore
every single word that contains an "a"; but to get a valid anagram we
have to find some word or words that contain a "b".  Only after we
have matched and extracted the "b" (and probably some other
characters) do we have to worry about any other subwords.

3. In cases where the test string has more than one of the same
character (such as "aaer", formed from "area"), extracting a matching
word may leave us looking in the same word group.  "aaer" minus "ar",
for example, leaves "ae"; we would have to search through the "a"
group again.  In this case, we search forward from our current
position in the group, rather than restarting the search at the
beginning of the same group.  This prevents us from finding anagram
collections that have the same words in different orders, saving time
and greatly reducing the output.

4. We can assume that, below a given size, we will not find any
interesting matches for the test string.  The program will not load
words in to the dictionary that are below this size, and will
abandon a recursive search if the test string is below this size.
This prevents us from matching the word "a" in the test string
"aaaabcceelrtu" ("baccalaureate") and then doing a search on
"aaabcceelrtu".

5. It turns out that, stylistically, proper names don't make
interesting anagrams.  Any words that have uppercase characters
(according to "isupper") are not placed in the dictionary.



The WordCollection class reads its dictionary from an InputIterator
object and sends its matches to an OutputIterator object.  These are
template parameters that must match the corresponding STL iterator
interfaces.

While the code given in "main()" simply binds standard input and
standard output to iterators, there are other potential designs.  For
example, loading the dictionary into memory is a major bottleneck.  If
we could load the dictionary once and then search through several
names in sequence (say, one per command line argument), that would
significantly speed up the program.  The iterator-based interface
makes this trivial.

If the program were supposed to deal with *hundreds* of names (say, if
it were a daemon listening on a network port), then it would be
worthwhile to pre-load and pre-canonicalize the entire dictionary.  We
could also do culling steps 4 and 5, and the partioning step 2, at
initialization.

*/


// Use vectors of characters as words.  Strings don't quite fit into
// the STL interface scheme.
typedef vector<char> word;

// Don't bother trying to perform a match if the word is less than
// this many characters long.
const size_t MINIMAL_WORD_SIZE = 3;

bool
issmallword(const word &w)
{
  return w.size() < MINIMAL_WORD_SIZE;
}

// Returns true if the word has any uppercase characters, false
// otherwise.
bool
hasuppercase(const word &w)
{
  return (find_if(w.begin(), w.end(), ptr_fun(isupper)) != w.end());
}

// Takes an input word returns its canonical form.
word
canonicalize(const word &w)
{
  word tmp;
  // We shall always downcase during the canonicalization process.
  // The dictionary words should always be in lowercase, but the
  // program argument may be capitalized.
  transform(w.begin(), w.end(), back_inserter(tmp), ptr_fun(tolower));
  tmp.erase(remove_if(tmp.begin(), tmp.end(), not1(ptr_fun(isalpha))),
             tmp.end());
  sort(tmp.begin(), tmp.end());
  return tmp;
}

ostream &operator<<(ostream &out, const word &w)
{
  word::const_iterator i=w.begin();
  while (i != w.end())
    out << *i++;
  return out;
}

istream &operator>>(istream &in, word &w)
{
  string s;
  in >> s;
  w = word(s.begin(), s.end());
  return in;
}


// The MatchStack class allows us to keep track of the dictionary
// words that have matched our input string.  When a match is found,
// it is pushed onto the stack, and the stack is then passed along to
// a recursive call of the search function.
//
// Each MatchStack takes an OutputIterator object at construction.  At
// any point, we can call the "send()" method to send the contents of
// the MatchStack (concatenated into a single word) to that iterator
// (and advance the iterator).
template <typename OutputIterator>
class MatchStack 
  :private vector<word>
{
public:
  MatchStack(OutputIterator &out_);
  virtual ~MatchStack() {}
  vector<word>::push_back;
  vector<word>::pop_back;
  void send();
private:
  OutputIterator &out;
  MatchStack();
};

template <typename OutputIterator>
MatchStack<OutputIterator>::MatchStack(OutputIterator &out_)
  : vector<word>(), out(out_)
{}

template <typename OutputIterator>
void
MatchStack<OutputIterator>::send()
{
  word accum;
  for (vector<word>::iterator i=begin(); i!=end(); ++i)
    {
      if (i!=begin())
        accum.push_back(' ');
      accum.insert(accum.end(), (*i).begin(), (*i).end());
    }
  *out++ = accum;
}


// WordCollection implements the loading and scanning algorithms for
// our search program.  The run-time data structures could go anywhere
// in the program, since we don't have any higher-level architecture
// dictating their placement.  For now, they are simply bundled into
// WordCollection as well.  Similarly, the WordCollection interface is
// designed to make the driver code in "main()" as simple as possible,
// for lack of any other strategy.
template <typename InputIterator, typename OutputIterator>
class WordCollection
{
public:
  WordCollection(OutputIterator &out, const word &n);
  ~WordCollection();

  void load(InputIterator &in, const InputIterator &eoi);
  void scan();

private:
  // "matches" accumulates words that we have discovered during our
  // search.
  MatchStack<OutputIterator> matches;

  // "name" is the canonical word which will provide the source
  // letters for the anagrams.
  const word name;

  // We will be matching on sorted vectors of characters, but we will
  // need to print them in their original format.  We choose to trade
  // space for time, and keep track of both in the DElem structure.
  struct DElem
  {
    word original, canonical;
  };

  // "dict" holds all the words that might help form anagrams of
  // "name".  The are collected in unsorted lists of "DElem" objects,
  // partitioned on the first character of the canonical form.
  typedef map< char, list<DElem> > dict_t;
  dict_t dict;

  // Allows us to bracket the search space for a particular collection
  // of "DElem" objects.
  typedef list<DElem>::const_iterator entry_t;

  void scan(const word &test_str);
  void scan_group(const word &test_str,
                  entry_t entry, entry_t end_of_group);
  void scan_select(const word &test_str,
                   entry_t entry, entry_t end_of_group,
                   char curr_group_id);

  // unused
  WordCollection();
};

template <typename InputIterator, typename OutputIterator>
WordCollection<InputIterator, OutputIterator>::
WordCollection(OutputIterator &out, const word &n)
  :matches(out), name(canonicalize(n)), dict()
{
  cerr << "canonical argument: " << name << endl;
}

template <typename InputIterator, typename OutputIterator>
WordCollection<InputIterator, OutputIterator>::~WordCollection()
{}

// Load a collection of words from the input iterator, storing the
// original and canonical forms in the appropriate list if any only if
// this will be an anagram component (according to the rules given at
// the top of the file).  "eoi" is the iterator signalling the end of
// the collection.
template <typename InputIterator, typename OutputIterator>
void
WordCollection<InputIterator, OutputIterator>::
load(InputIterator &in, const InputIterator &eoi)
{
  long count = 0;
  while (in != eoi)
    {
      DElem temp;
      temp.original = *in++;
      if (! issmallword(temp.original) && ! hasuppercase(temp.original))
        {
          temp.canonical = canonicalize(temp.original);
          if (includes(name.begin(), name.end(),
                       temp.canonical.begin(), temp.canonical.end()))
            {
              dict[temp.canonical[0]].push_back(temp);
              ++count;
            }
        }
    }
  cerr << "collection has " << count << " entries" << endl;
}

// Start iterating forward from "entry".  These are all words that
// could form "test_str".  For each candiate, push it onto "matches"
// (stored in the object), and extract its characters from "test_str".
//
// We then call "scan_select" to determine what to do next.
//
// "scan_group()" requires that "test_str" be at least of minimum
// length (as determined by "issmallword()").  The calling function
// should not call "scan_group()" at all if "test_str" is too small.
template <typename InputIterator, typename OutputIterator>
void
WordCollection<InputIterator, OutputIterator>::
scan_group(const word &test_str,
           entry_t entry,
           entry_t end_of_group)
{
  for (; entry!=end_of_group; ++entry)
    if (includes(test_str.begin(), test_str.end(),
                 (*entry).canonical.begin(), (*entry).canonical.end()))
      {
        word new_str;
        set_difference(test_str.begin(), test_str.end(),
                       (*entry).canonical.begin(), (*entry).canonical.end(),
                       back_inserter(new_str));

        matches.push_back((*entry).original);
        scan_select(new_str, entry, end_of_group, test_str[0]);
        matches.pop_back();
      }
}

// This method encodes the decision logic for the algorithm, once we
// have matched a subword and extracted its characters.  Depending on
// the remaining characters (provided in the "test_str" parameter), we
// have several different courses of action.
//
// If the remaining set of characters is empty, then "matches" must
// contain a perfect match of the original word; we can print out all
// the accumulated matched words instead of performing recursion.
//
// If the remaining set of characters is too small, we do nothing and
// exit.
//
// Otherwise, determine the bounds for the next group of candidate
// words (based on the first character in the canonical form), and do
// a recursive call to match the remaining letters.
//
// "entry" and "end_of_group" delimit the current dictionary search
// group, and "curr_group_id" gives the character identifier shared by
// all elements in that group.
template <typename InputIterator, typename OutputIterator>
void
WordCollection<InputIterator, OutputIterator>::
scan_select(const word &test_str,
            WordCollection::entry_t entry,
            WordCollection::entry_t end_of_group,
            char curr_group_id)
{
  if (test_str.empty())
    matches.send();
  else if (issmallword(test_str))
    ;
  else if (test_str[0]==curr_group_id)
    {
      // If "test_str" is in the same search group as
      // our current one, only search forward from our
      // current position, to prevent double matches.
      WordCollection::entry_t new_entry = entry;
      scan_group(test_str, ++new_entry, end_of_group);
    }
  else
    // If "test_str" is in a different group from our
    // current one, we have to redetermine the
    // group bounds.
    scan(test_str);
}

// Determine the search bounds for this test string, and do the
// search.
template <typename InputIterator, typename OutputIterator>
void
WordCollection<InputIterator, OutputIterator>::scan(const word &test_str)
{
  dict_t::const_iterator i = dict.find(test_str[0]);
  if (i != dict.end())
    scan_group(test_str, (*i).second.begin(), (*i).second.end());
}

// Starts off the recursive search.  "name" has to become a function
// argument, because we will be overriding it as we do our depth-first
// search into the dictionary.
template <typename InputIterator, typename OutputIterator>
void
WordCollection<InputIterator, OutputIterator>::scan()
{
  if (! issmallword(name))
    scan(name);
}

// Takes one command line argument, the string that forms the basis
// for the anagrams.  The dictionary is read from stdin and the
// results are sent to stdout.

int
main(int argc, char *argv[])
{
  if (argc != 2)
    return EXIT_FAILURE;
  word name(argv[1], argv[1]+strlen(argv[1]));

  typedef istream_iterator<word> in_t;
  in_t in(cin), eoi;

  typedef ostream_iterator<word> out_t;
  out_t out(cout, "\n");

  WordCollection<in_t, out_t> collection(out, name);
  collection.load(in, eoi);
  collection.scan();
  return 0;
}