Totals
bgl_time_remove_vertex()
{
    GraphType g;
    start_deadman(2);
    while (!had_alarm && boost::num_vertices(g)<MAX_VERTICES)
        boost::add_vertex(g);
    GraphSize gsize = bgl_size(g);
    size_t nv_orig = gsize.first;

    // Vertex removal is SO SLOW that we need more time to measure it accurately.  To quote from chapter 11 "Performance
    // Guidelines" of the the "Boost Graph Library: User Guide and Reference Manual" book,
    //     Other variations [than list-list] of adjacency list perform horribly on this operation because its
    //     implementation is not of constant time complexity.
    start_deadman(6);
    Sawyer::Stopwatch t;
    for (size_t i=0; i<nv_orig && !had_alarm; ++i) {
        // Note that this won't work generically.  It's only good for graphs where vertices are numbered sequentially across
        // the entire graph.
        typename boost::graph_traits<GraphType>::vertex_descriptor v = rand() % boost::num_vertices(g);
        boost::remove_vertex(v, g);
    }
    t.stop();
    size_t nremoved = nv_orig - boost::num_vertices(g);
    return report("vert erase", gsize, nremoved, t, "verts/s");
}

static Totals
report(const std::string &title, const GraphSize gsize, size_t count, const Sawyer::Stopwatch &t, const std::string &units)
{
    printf("  %-16s (%13s %13s) %13s / %6.3f  ",
           title.c_str(),
           pretty(gsize.first).c_str(), pretty(gsize.second).c_str(),
           pretty(count).c_str(), t.report());
    double rate = count / t.report();
    if (rate >= 10e9) {
        printf("%13g", rate);
    } else {
        uint64_t irate = rate;
        printf("%13s", pretty(irate).c_str());
    }
    printf(" %s\n", units.c_str());
    return Totals(count, t.report());
}

// usage: testSort NTHINGS NTHREADS
int main(int argc, char *argv[]) {
    size_t nvalues = 16;
    size_t nthreads = 1;
    if (argc>1)
        nvalues = strtoul(argv[1], NULL, 0);
    if (argc>2)
        nthreads = strtoul(argv[2], NULL, 0);
    
    std::cerr <<"Generating " <<nvalues <<" values... ";
    Sawyer::Stopwatch generation;
    LinearCongruentialGenerator random;
    std::vector<Thing> values;
    values.reserve(nvalues);
    for (size_t i=0; i<nvalues; ++i) {
        static const int maxval = 1000000;
        values.push_back(Thing(random() % maxval, random() % maxval));
    }
    std::cerr <<"done (" <<generation.stop() <<" seconds)\n";
                         
    std::cerr <<"Sorting with " <<nthreads <<" threads... ";
    Sawyer::Stopwatch sorting;
    rose::ParallelSort::quicksort(&values[0], &values[0]+values.size(), compare, nthreads);
    std::cerr <<"done (" <<sorting.stop() <<" seconds)\n";

    std::cerr <<"Checking results...\n";
    size_t nfailures = 0;
    static const size_t failureLimit = 100;
    for (size_t i=1; i<values.size() && nfailures<failureLimit; ++i) {
        if (!compare(values[i-1], values[i]) && compare(values[i], values[i-1])) {
            std::cerr <<"sort failed: values[" <<i-1 <<", " <<i <<"] = (" <<values[i-1] <<", " <<values[i] <<")\n";
            ++nfailures;
        }
    }
    if (nfailures>=failureLimit)
        std::cerr <<"additional failures suppressed.\n";

    return nfailures ? 1 : 0;
}