X-Authentication-Warning: delorie.com: mailnull set sender to djgpp-bounces using -f
From: Alex Vinokur <alexvn AT bigfoot DOT com>
Newsgroups: comp.software.measurement,comp.lang.c++,comp.os.msdos.djgpp,comp.games.development.programming.misc
Subject: Re: C/C++ Program Perfometer
Date: Mon, 11 Mar 2002 11:40:39 +0200
Lines: 354
Message-ID: <3C8C7B97.E4B5CA9C@bigfoot.com>
References: <3C848503 DOT AB2A4938 AT bigfoot DOT com> <3C84CF9B DOT AA99EFA8 AT bigfoot DOT com>
NNTP-Posting-Host: 62.90.123.5
Mime-Version: 1.0
Content-Type: text/plain; charset=koi8-r
Content-Transfer-Encoding: 7bit
X-Trace: fu-berlin.de 1015839578 15244295 62.90.123.5 (16 [79865])
X-Mailer: Mozilla 4.7 [en] (Win98; I)
X-Accept-Language: en
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Reply-To: djgpp AT delorie DOT com

Performance of the find() algorithm/method in vector, list, set, map
was measured when using C/C++ Program Perfometer at
  http://groups.google.com/groups?selm=3C84CF9B.AA99EFA8%40bigfoot.com .



===============================================================
gpp : GNU C++ version 2.95.3 20010315/djgpp (release) (djgpp)
      compiled by GNU C version 2.95.3 20010315/djgpp (release).
---------
Windows98
===============================================================



  --- No optimization ---
  #=========================================================
  # Comparison Group#1 of 1 : find method vs. find algorithm
  #---------------------------------------------------------
  #   Resource Name       : user time used
  #   Resource Cost Unit  : uclock
  #   Resource State Unit : uclock
  #=========================================================
   : ----------------------------------------------------------------------
   : f2 : demo3.c   #63 : find algorithm - vector size 100  ->        11091
   : f2 : demo3.c   #75 : find algorithm - list size 100    ->        59514
   : f2 : demo3.c   #88 : find algorithm - set size 100     ->       145631
   : f2 : demo3.c  #101 : find method    - set size 100     ->        18626
   : f2 : demo3.c  #114 : find method    - map size 100     ->        18991
   : f2 : demo3.c  #128 : find algorithm - vector size 1000 ->        87894
   : f2 : demo3.c  #140 : find algorithm - list size 1000   ->       567694
   : f2 : demo3.c  #153 : find algorithm - set size 1000    ->      1619926
   : f2 : demo3.c  #166 : find method    - set size 1000    ->        24773
   : f2 : demo3.c  #179 : find method    - map size 1000    ->        24474
   : ----------------------------------------------------------------------



                --- Optimization O1 ---
  #=========================================================
  # Comparison Group#1 of 1 : find method vs. find algorithm
  #---------------------------------------------------------
  #   Resource Name       : user time used
  #   Resource Cost Unit  : uclock
  #   Resource State Unit : uclock
  #=========================================================
   : ----------------------------------------------------------------------
   : f2 : demo3.c   #63 : find algorithm - vector size 100  ->         4227
   : f2 : demo3.c   #75 : find algorithm - list size 100    ->        12710
   : f2 : demo3.c   #88 : find algorithm - set size 100     ->        27015
   : f2 : demo3.c  #101 : find method    - set size 100     ->         2106
   : f2 : demo3.c  #114 : find method    - map size 100     ->         2986
   : f2 : demo3.c  #128 : find algorithm - vector size 1000 ->        36062
   : f2 : demo3.c  #140 : find algorithm - list size 1000   ->       153180
   : f2 : demo3.c  #153 : find algorithm - set size 1000    ->       461163
   : f2 : demo3.c  #166 : find method    - set size 1000    ->         2257
   : f2 : demo3.c  #179 : find method    - map size 1000    ->         2995
   : ----------------------------------------------------------------------



                --- Optimization O2 ---
  #=========================================================
  # Comparison Group#1 of 1 : find method vs. find algorithm
  #---------------------------------------------------------
  #   Resource Name       : user time used
  #   Resource Cost Unit  : uclock
  #   Resource State Unit : uclock
  #=========================================================
   : ----------------------------------------------------------------------
   : f2 : demo3.c   #63 : find algorithm - vector size 100  ->         4336
   : f2 : demo3.c   #75 : find algorithm - list size 100    ->         7350
   : f2 : demo3.c   #88 : find algorithm - set size 100     ->        25985
   : f2 : demo3.c  #101 : find method    - set size 100     ->         1730
   : f2 : demo3.c  #114 : find method    - map size 100     ->         1905
   : f2 : demo3.c  #128 : find algorithm - vector size 1000 ->        37089
   : f2 : demo3.c  #140 : find algorithm - list size 1000   ->       130727
   : f2 : demo3.c  #153 : find algorithm - set size 1000    ->       458502
   : f2 : demo3.c  #166 : find method    - set size 1000    ->         1945
   : f2 : demo3.c  #179 : find method    - map size 1000    ->         2341
   : ----------------------------------------------------------------------



                --- Optimization O3 ---
  #=========================================================
  # Comparison Group#1 of 1 : find method vs. find algorithm
  #---------------------------------------------------------
  #   Resource Name       : user time used
  #   Resource Cost Unit  : uclock
  #   Resource State Unit : uclock
  #=========================================================
   : ----------------------------------------------------------------------
   : f2 : demo3.c   #63 : find algorithm - vector size 100  ->         3987
   : f2 : demo3.c   #75 : find algorithm - list size 100    ->         6646
   : f2 : demo3.c   #88 : find algorithm - set size 100     ->        25572
   : f2 : demo3.c  #101 : find method    - set size 100     ->         1639
   : f2 : demo3.c  #114 : find method    - map size 100     ->         1688
   : f2 : demo3.c  #128 : find algorithm - vector size 1000 ->        35102
   : f2 : demo3.c  #140 : find algorithm - list size 1000   ->       124117
   : f2 : demo3.c  #153 : find algorithm - set size 1000    ->       442743
   : f2 : demo3.c  #166 : find method    - set size 1000    ->         1915
   : f2 : demo3.c  #179 : find method    - map size 1000    ->         2182
   : ----------------------------------------------------------------------





// =================== File demo.h : BEGIN ====================
#ifndef _DEMO_H
#define _DEMO_H

#include "adapt.h"

#define TURN_ON_uclock(x) TURN_ON (uclock_t, uclock_t, RESOURCE_user_time_used, x)

void f2 (void);

#endif

// =================== File demo.h : END ======================




// =================== File demo.c : BEGIN ====================
#include "demo.h"

void SetEnvIt ()
{
  SetTotalTests (25);
  SetScaleAndTotalIterations (10000, 100000);
}


void MeasureIt ()
{
}


void CompareIt ()
{
  CompareFunc ("find method vs. find algorithm", f2);
}


// =================== File demo.c : END ======================



// =================== File demo3.c : BEGIN ====================
#include "demo.h"

//---------------------------
#define SIZE_1 100
#define SIZE_2 1000


// ==========================
void f2 (void)
{
  // ------ Preparation ------
ostringstream osstr;

const size_t median_value_1 = SIZE_1/2;
const size_t median_value_2 = SIZE_2/2;

vector<int> int_vector_1;
vector<int> int_vector_2;

list<int> int_list_1;
list<int> int_list_2;

set<int> int_set_1;
set<int> int_set_2;

map<int, string> int_map_1;
map<int, string> int_map_2;

  for (int i = 0; i < SIZE_1; i++)
  {
    int_vector_1.push_back(i);
    int_list_1.push_back(i);
    int_set_1.insert(i);
    int_map_1[i] = "AAAAAAAAAA";
  }


  for (int i = 0; i < SIZE_2; i++)
  {
    int_vector_2.push_back(i);
    int_list_2.push_back(i);
    int_set_2.insert(i);
    int_map_2[i] = "BBBBBBBBBB";
  }

  assert (int_vector_1.size() == SIZE_1);
  assert (int_list_1.size()   == SIZE_1);
  assert (int_set_1.size()    == SIZE_1);
  assert (int_map_1.size()    == SIZE_1);

  assert (int_vector_2.size() == SIZE_2);
  assert (int_list_2.size()    == SIZE_2);
  assert (int_set_2.size()    == SIZE_2);
  assert (int_map_2.size()    == SIZE_2);


  // -------- find algorithm : int_vector_1 --------
  {
    osstr.str(string());
    osstr << "find algorithm - vector size "
          <<  int_vector_1.size();

    TURN_ON_uclock(osstr.str())
    {
      find (int_vector_1.begin(), int_vector_1.end(), median_value_1);
    }
  }

  // -------- find algorithm : int_list_1 --------
  {
    osstr.str(string());
    osstr << "find algorithm - list size "
          <<  int_list_1.size();

    TURN_ON_uclock(osstr.str())
    {
      find (int_list_1.begin(), int_list_1.end(), median_value_1);
    }
  }


  // -------- find algorithm : int_set_1 --------
  {
    osstr.str(string());
    osstr << "find algorithm - set size "
          <<  int_set_1.size();

    TURN_ON_uclock(osstr.str())
    {
      find (int_set_1.begin(), int_set_1.end(), median_value_1);
    }
  }


  // -------- find method : int_set_1 --------
  {
    osstr.str(string());
    osstr << "find method    - set size "
          <<  int_set_1.size();

    TURN_ON_uclock(osstr.str())
    {
      int_set_1.find (median_value_1);
    }
  }


  // -------- find method : int_map_1 --------
  {
    osstr.str(string());
    osstr << "find method    - map size "
          <<  int_map_1.size();

    TURN_ON_uclock(osstr.str())
    {
      int_map_1.find (median_value_1);
    }
  }



  // -------- find algorithm : int_vector_2 --------
  {
    osstr.str(string());
    osstr << "find algorithm - vector size "
          <<  int_vector_2.size();

    TURN_ON_uclock(osstr.str())
    {
      find (int_vector_2.begin(), int_vector_2.end(), median_value_2);
    }
  }

  // -------- find algorithm : int_list_2 --------
  {
    osstr.str(string());
    osstr << "find algorithm - list size "
          <<  int_list_2.size();

    TURN_ON_uclock(osstr.str())
    {
      find (int_list_2.begin(), int_list_2.end(), median_value_2);
    }
  }


  // -------- find algorithm : int_set_2 --------
  {
    osstr.str(string());
    osstr << "find algorithm - set size "
          <<  int_set_2.size();

    TURN_ON_uclock(osstr.str())
    {
      find (int_set_2.begin(), int_set_2.end(), median_value_2);
    }
  }


  // -------- find method : int_set_2 --------
  {
    osstr.str(string());
    osstr << "find method    - set size "
          <<  int_set_2.size();

    TURN_ON_uclock(osstr.str())
    {
      int_set_2.find (median_value_2);
    }
  }


  // -------- find method : int_map_2 --------
  {
    osstr.str(string());
    osstr << "find method    - map size "
          <<  int_map_2.size();

    TURN_ON_uclock(osstr.str())
    {
      int_map_2.find (median_value_2);
    }
  }



} // f2

// =================== File demo3.c : END ======================



  ===========================
  Alex Vinokur
    mailto:alexvn AT bigfoot DOT com
    mailto:alexvn AT go DOT to
    http://up.to/alexvn
    http://go.to/alexv_math
  ===========================