assorted-commits

[Assorted-commits] SF.net SVN: assorted: [402] numa-bench/trunk/src/malloc.bash

[<yan...@us...>]

Revision: 402
          http://assorted.svn.sourceforge.net/assorted/?rev=402&view=rev
Author:   yangzhang
Date:     2008-02-12 23:58:40 -0800 (Tue, 12 Feb 2008)

Log Message:
-----------
added malloc runner (out of date with malloc.cc)

Added Paths:
-----------
    numa-bench/trunk/src/malloc.bash

Added: numa-bench/trunk/src/malloc.bash
===================================================================
--- numa-bench/trunk/src/malloc.bash	                        (rev 0)
+++ numa-bench/trunk/src/malloc.bash	2008-02-13 07:58:40 UTC (rev 402)
@@ -0,0 +1,19 @@
+#!/usr/bin/env bash
+
+set -o errexit -o nounset
+
+function run {
+  ./malloc 16 $*
+}
+
+#echo '--- 100MB * 1, seq ---'
+#run  100000000  1 0
+#
+#echo '--- 1GB * 1, seq ---'
+#run 1000000000  1 0
+#
+#echo '--- 100MB * 10, seq ---'
+#run  100000000 10 0
+
+echo '--- 100MB * 1, rand ---'
+run  100000000  1 1


Property changes on: numa-bench/trunk/src/malloc.bash
___________________________________________________________________
Name: svn:executable
   + *


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted: [401] numa-bench/trunk/src/malloc.cc

[<yan...@us...>]

Revision: 401
          http://assorted.svn.sourceforge.net/assorted/?rev=401&view=rev
Author:   yangzhang
Date:     2008-02-12 23:58:13 -0800 (Tue, 12 Feb 2008)

Log Message:
-----------
beefed up the test

Modified Paths:
--------------
    numa-bench/trunk/src/malloc.cc

Modified: numa-bench/trunk/src/malloc.cc
===================================================================
--- numa-bench/trunk/src/malloc.cc	2008-02-13 07:58:00 UTC (rev 400)
+++ numa-bench/trunk/src/malloc.cc	2008-02-13 07:58:13 UTC (rev 401)
@@ -1,7 +1,7 @@
 // Questions this program answers:
 //
 // - Does malloc tend to allocate locally?
-//   - Yes. Times working from local node is lower.
+//   - TODO!
 // - How much does working from another node affect throughput?
 //   - A bit: 647x from local, 649x from neighbor, 651x from remote
 // - Is there difference from repeatedly fetching the same (large) area n times
@@ -21,6 +21,7 @@
 
 #include <cstdlib>
 #include <iostream>
+#include <iomanip>
 
 #include <sched.h>
 
@@ -35,77 +36,166 @@
 using namespace commons;
 using namespace std;
 
+struct config
+{
+  /**
+   * The number of cores to test. This is a parameter (rather than
+   * auto-detected) because it additionally serves to mean the number of cores
+   * we want to test in parallel. As this program evolves, these may be
+   * separated.
+   */
+  const int ncores;
+
+  /**
+   * Size in bytes of the buffer to chew.
+   */
+  const size_t size;
+
+  /**
+   * Number of repetitions to chew.
+   */
+  const int nreps;
+
+  /**
+   * Perform rand access, otherwise sequential scan.
+   */
+  const bool shuffle;
+
+  /**
+   * Chew in parallel, otherwise each core chews serially.
+   */
+  const bool par;
+
+  /**
+   * Pin thread i to core i, otherwise let the OS manage things.
+   */
+  const bool pin;
+
+  /**
+   * Chew my own memory, otherwise chew the given (shared) memory.
+   */
+  const bool local;
+
+  /**
+   * Do writes, otherwise just do reads.
+   */
+  const bool write;
+};
+
 /**
  * \param pp The start of the buffer to chew.
- * \param core Which core to pin our thread to.
- * \param size The size of the buffer.
- * \param nreps The number of times to chew through the buffer.
- * \param shuffle If false, sequentially chew through; otherwise, randomly
- *     shuffle the indexes we chew through.
+ * \param cpu Which CPU to pin our thread to.
+ * \param config The experiment configuration parameters.
  */
 void*
-chew(void* pp, unsigned int core, size_t size, unsigned int nreps, bool shuffle)
+chew(void* pp, unsigned int cpu, const config & config, const char* label)
 {
-  int* p = (int*) pp;
-  const size_t count = size / sizeof(int);
-  pid_t pid = gettid();
+  int* p = (int*) (config.local ? malloc(config.size) : pp);
+  const size_t count = config.size / sizeof(int);
   timer t(": ");
 
-  // Pin this thread to core `core`.
-  cpu_set_t cs;
-  CPU_ZERO(&cs);
-  CPU_SET(core, &cs);
-  sched_setaffinity(pid, sizeof(cs), &cs);
+  // Pin this thread to cpu `cpu`.
+  if (config.pin) {
+    pin_thread(cpu);
+  }
 
-  // Write sequentially to the memory region.
-  if (shuffle) {
-    for (unsigned int c = 0; c < nreps; c++) {
-      for (size_t i = 0; i < count; i++) {
-        // NOTE: Using r as the index assumes that rand generates large-enough
-        // values.
-        int r = rand();
-        p[r % count] += r;
+  if (config.write) {
+    // Write to the region.
+    if (config.shuffle) {
+      // Random access into the memory region.
+      for (unsigned int c = 0; c < config.nreps; c++) {
+        for (size_t i = 0; i < count; i++) {
+          // NOTE: Using r as the index assumes that rand generates large-enough
+          // values.
+          int r = rand();
+          p[r % count] += r;
+        }
       }
+    } else {
+      // Sequential scan through the memory region.
+      for (unsigned int c = 0; c < config.nreps; c++) {
+        for (size_t i = 0; i < count; i++) {
+          p[i] += rand();
+        }
+      }
     }
   } else {
-    for (unsigned int c = 0; c < nreps; c++) {
-      for (size_t i = 0; i < count; i++) {
-        p[i] += rand();
+    // Only read from the region.
+    int sum = 0;
+    if (config.shuffle) {
+      // Random access into the memory region.
+      for (unsigned int c = 0; c < config.nreps; c++) {
+        for (size_t i = 0; i < count; i++) {
+          // NOTE: Using r as the index assumes that rand generates large-enough
+          // values.
+          sum += p[rand() % count];
+        }
       }
+    } else {
+      // Sequential scan through the memory region.
+      for (unsigned int c = 0; c < config.nreps; c++) {
+        for (size_t i = 0; i < count; i++) {
+          sum += p[i] + rand();
+        }
+      }
     }
+    cout << sum << endl;
   }
 
   // Print the elapsed time.
-  cout << core;
+  cout << label << cpu;
   t.print();
+
+  if (config.local) free(p);
+
   return NULL;
 }
 
 int
 main(int argc, char** argv)
 {
-  if (argc < 5) {
-    cerr << argv[0] << " <ncores> <size> <nreps> <shuffle>" << endl;
+  // So that our global shared malloc takes place on the CPU 0's node.
+  pin_thread(0);
+
+  if (argc < 9) {
+    cerr << argv[0] <<
+      " <ncores> <size> <nreps> <shuffle> <par> <pin> <local> <write>" << endl;
     return 1;
   }
 
-  // Parse command-line arguments.
-  const int ncores = atoi(argv[1]);
-  const size_t size = atoi(argv[2]);
-  const int nreps = atoi(argv[3]);
-  const bool shuffle = atoi(argv[4]);
+  // Parse command-line arguments. TODO
+  const config config = { 
+    atoi(argv[1]),
+    atoi(argv[2]),
+    atoi(argv[3]),
+    atoi(argv[4]),
+    atoi(argv[5]),
+    atoi(argv[6]),
+    atoi(argv[7]),
+    atoi(argv[8])
+  };
 
-  void *p = malloc(size);
+  checkmsg(RAND_MAX > config.size / sizeof(int), "PRNG range not large enough");
 
+  void *p = malloc(config.size);
+
   // Warmup.
-  cout << "warmup: ";
-  chew(p, 0, size, nreps, shuffle);
+  chew(p, 0, config, "warmup: ");
 
-  // Chew the memory area from each core.
-  for (int i = 0; i < ncores; i++) {
-    pthread_t t;
-    check((t = spawn(bind(chew, p, i, size, nreps, shuffle))) != 0);
-    check(pthread_join(t, NULL) == 0);
+  if (config.par) {
+    // Chew the memory area from each core in parallel (and also chew own).
+    pthread_t ts[config.ncores];
+    for (int i = 0; i < config.ncores; i++) {
+      ts[i] = spawn(bind(chew, p, i, ref(config), ""));
+    }
+    for (int i = 0; i < config.ncores; i++) {
+      check(pthread_join(ts[i], NULL) == 0);
+    }
+  } else {
+    // Chew the memory area from each core in sequence.
+    for (int i = 0; i < config.ncores; i++) {
+      chew(p, i, config, "");
+    }
   }
 
   free(p);


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted: [400] numa-bench/trunk/src/avail.cc

[<yan...@us...>]

Revision: 400
          http://assorted.svn.sourceforge.net/assorted/?rev=400&view=rev
Author:   yangzhang
Date:     2008-02-12 23:58:00 -0800 (Tue, 12 Feb 2008)

Log Message:
-----------
added libnuma env info

Modified Paths:
--------------
    numa-bench/trunk/src/avail.cc

Modified: numa-bench/trunk/src/avail.cc
===================================================================
--- numa-bench/trunk/src/avail.cc	2008-02-13 03:26:47 UTC (rev 399)
+++ numa-bench/trunk/src/avail.cc	2008-02-13 07:58:00 UTC (rev 400)
@@ -1,7 +1,38 @@
+//
+// Dump environment information provided by libnuma.
+//
+
+#include <iostream>
+#include <iomanip>
 #include <numa.h>
 
+#include <commons/check.h>
+
+using namespace commons;
+using namespace std;
+
 int
 main()
 {
-  return numa_available() < 0;
+  if (numa_available() < 0) {
+    cout << "no numa" << endl;
+  } else {
+    for (int node = 0; node <= numa_max_node(); node++) {
+      // Print node sizes.
+      long long free, size = numa_node_size64(node, &free);
+      check(-1 != size);
+      cout << "node " << node << " size " << size << " free " << free << " cpus ";
+
+      // Print node CPUs.
+      const int buflen = 512;
+      unsigned long buffer[buflen];
+      check(0 == numa_node_to_cpus(node, buffer, buflen));
+      // TODO # cpus?
+      for (int i = 0; i < 1; i++) {
+        cout << hex << setfill('0') << setw(4) << buffer[i] << dec << ' ';
+      }
+      cout << endl;
+    }
+  }
+  return 0;
 }


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted: [399] numa-bench/trunk/src/Makefile

[<yan...@us...>]

Revision: 399
          http://assorted.svn.sourceforge.net/assorted/?rev=399&view=rev
Author:   yangzhang
Date:     2008-02-12 19:26:47 -0800 (Tue, 12 Feb 2008)

Log Message:
-----------
added optimization

Modified Paths:
--------------
    numa-bench/trunk/src/Makefile

Modified: numa-bench/trunk/src/Makefile
===================================================================
--- numa-bench/trunk/src/Makefile	2008-02-13 03:26:37 UTC (rev 398)
+++ numa-bench/trunk/src/Makefile	2008-02-13 03:26:47 UTC (rev 399)
@@ -1,5 +1,5 @@
 COMMONS := $(wildcard commons/*.h)
-CXX = g++-4.2 -I. -lnuma -lpthread -o $@ $<
+CXX = g++-4.2 -O3 -I. -lnuma -lpthread -o $@ $<
 
 # all: avail cache malloc threads
 all: malloc


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted: [398] numa-bench/trunk/src/malloc.cc

[<yan...@us...>]

Revision: 398
          http://assorted.svn.sourceforge.net/assorted/?rev=398&view=rev
Author:   yangzhang
Date:     2008-02-12 19:26:37 -0800 (Tue, 12 Feb 2008)

Log Message:
-----------
calling rand() in seq to make the test more fair; writing by ints not chars; added some notes

Modified Paths:
--------------
    numa-bench/trunk/src/malloc.cc

Modified: numa-bench/trunk/src/malloc.cc
===================================================================
--- numa-bench/trunk/src/malloc.cc	2008-02-12 22:15:13 UTC (rev 397)
+++ numa-bench/trunk/src/malloc.cc	2008-02-13 03:26:37 UTC (rev 398)
@@ -11,6 +11,8 @@
 //   - Huge difference. Also magnifies the locality effects more.
 //   - 1700 from local, 1990 from one neighbor, 2020 from another neighbor,
 //     and 2310 from remote.
+// - What's the difference between reading and writing?
+//   - TODO!
 // - Can we observe prefetching's effects? (Random access but chew the full
 //   cache line of data.)
 //   - TODO!
@@ -42,9 +44,10 @@
  *     shuffle the indexes we chew through.
  */
 void*
-chew(void* pp, int core, size_t size, int nreps, bool shuffle)
+chew(void* pp, unsigned int core, size_t size, unsigned int nreps, bool shuffle)
 {
-  char* p = (char*) pp;
+  int* p = (int*) pp;
+  const size_t count = size / sizeof(int);
   pid_t pid = gettid();
   timer t(": ");
 
@@ -56,15 +59,18 @@
 
   // Write sequentially to the memory region.
   if (shuffle) {
-    for (int c = 0; c < nreps; c++) {
-      for (size_t i = 0; i < size; i++) {
-        p[rand() % size] = i;
+    for (unsigned int c = 0; c < nreps; c++) {
+      for (size_t i = 0; i < count; i++) {
+        // NOTE: Using r as the index assumes that rand generates large-enough
+        // values.
+        int r = rand();
+        p[r % count] += r;
       }
     }
   } else {
-    for (int c = 0; c < nreps; c++) {
-      for (size_t i = 0; i < size; i++) {
-        p[i] = i;
+    for (unsigned int c = 0; c < nreps; c++) {
+      for (size_t i = 0; i < count; i++) {
+        p[i] += rand();
       }
     }
   }


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted: [397] hash-join/trunk/src/hashjoin.cc

[<yan...@us...>]

Revision: 397
          http://assorted.svn.sourceforge.net/assorted/?rev=397&view=rev
Author:   yangzhang
Date:     2008-02-12 14:15:13 -0800 (Tue, 12 Feb 2008)

Log Message:
-----------
readded hit/miss debug

Modified Paths:
--------------
    hash-join/trunk/src/hashjoin.cc

Modified: hash-join/trunk/src/hashjoin.cc
===================================================================
--- hash-join/trunk/src/hashjoin.cc	2008-02-12 22:13:04 UTC (rev 396)
+++ hash-join/trunk/src/hashjoin.cc	2008-02-12 22:15:13 UTC (rev 397)
@@ -471,7 +471,7 @@
       }
     }
   }
-  // cout << "cpu " << pid << " hits " << hits << " misses " << misses << endl;
+  cout << "cpu " << pid << " hits " << hits << " misses " << misses << endl;
 }
 
 // vim:et:sw=2:ts=2


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted: [396] cpp-commons/trunk/src/commons/region.h

[<yan...@us...>]

Revision: 396
          http://assorted.svn.sourceforge.net/assorted/?rev=396&view=rev
Author:   yangzhang
Date:     2008-02-12 14:13:04 -0800 (Tue, 12 Feb 2008)

Log Message:
-----------
more space-saving; disabled debugs

Modified Paths:
--------------
    cpp-commons/trunk/src/commons/region.h

Modified: cpp-commons/trunk/src/commons/region.h
===================================================================
--- cpp-commons/trunk/src/commons/region.h	2008-02-12 21:58:51 UTC (rev 395)
+++ cpp-commons/trunk/src/commons/region.h	2008-02-12 22:13:04 UTC (rev 396)
@@ -7,6 +7,7 @@
 
 // XXX: debug
 #include <set>
+#include <vector>
 #include <pthread.h>
 
 namespace commons
@@ -17,7 +18,7 @@
   /**
    * Default chunk size is 100MB.
    */
-  const size_t default_chunk_size = 100000000;
+  const size_t default_chunk_size = 10000000;
 
   /**
    * A fixed-size buffer (really just a pair of length and pointer).
@@ -51,13 +52,13 @@
       top(0),
       refcount(0)
     {
-      cout << "created " << this << endl;
+      // cout << "created " << this << endl;
       chunks.push_back((chunk) {chunk_size, new char[chunk_size]});
     }
 
     ~mem_region()
     {
-      cout << "deleting" << endl;
+      // cout << "deleting" << endl;
       for (unsigned int i = 0; i < chunks.size(); i++) {
         delete [] chunks[i].data;
       }
@@ -68,18 +69,29 @@
 
     void *alloc_mem(size_t n)
     {
-      pthread_t t = pthread_self();
-      if (threads.insert(t).second)
-        cout << this << " -- " << t << endl;
+      // pthread_t t = pthread_self();
+      // if (threads.insert(t).second)
+        // cout << this << " -- " << t << endl;
 
-      if (top + n > chunks.back().size) {
+      chunk* last = &chunks.back();
+      if (top + n > last->size) {
         size_t sz = max(n, chunk_size);
-        chunks.push_back((chunk) {sz, new char[sz] });
-        top = 0;
+        chunk c = {sz, new char[sz]};
+        if (n > chunk_size) {
+          // cout << "insert " << this << endl;
+          chunks.insert(chunks.begin(), c);
+          return c.data;
+        } else {
+          // cout << "append " << this << endl;
+          chunks.push_back(c);
+          top = 0;
+          last = &chunks.back();
+        }
       }
+      // cout << "ALLOC " << this << endl;
       size_t old_top = top;
       top += n;
-      return chunks.back().data + old_top;
+      return last->data + old_top;
     }
   };
 


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted: [395] hash-join/trunk/src/hashjoin.cc

[<yan...@us...>]

Revision: 395
          http://assorted.svn.sourceforge.net/assorted/?rev=395&view=rev
Author:   yangzhang
Date:     2008-02-12 13:58:51 -0800 (Tue, 12 Feb 2008)

Log Message:
-----------
tweaks

Modified Paths:
--------------
    hash-join/trunk/src/hashjoin.cc

Modified: hash-join/trunk/src/hashjoin.cc
===================================================================
--- hash-join/trunk/src/hashjoin.cc	2008-02-12 19:16:18 UTC (rev 394)
+++ hash-join/trunk/src/hashjoin.cc	2008-02-12 21:58:51 UTC (rev 395)
@@ -1,3 +1,7 @@
+//
+// Hash Join
+//
+
 #include <memory>
 #include <cassert>
 #include <cstdio>
@@ -23,10 +27,6 @@
 
 // TODO: #include <boost/array.hpp>
 
-//
-// Hash Join
-//
-
 using namespace std;
 using namespace __gnu_cxx;
 using namespace commons;
@@ -46,14 +46,15 @@
   void
   resize(size_type hint)
   {
-    cout << "resizing " << this << " to " << hint << endl;
+    // cout << "resizing " << this << " to " << hint << endl;
     my_hash_map::resize(hint);
   }
 };
 
 // TODO use dependency injection!
 unsigned int ncpus = 1;
-const hmap::size_type map_size = 10000000;
+const hmap::size_type map_size = 1000000;
+const int min_bucket_size = 1000000;
 
 /**
  * Buckets are produced in the hash-partitioning phase. These are simple
@@ -224,7 +225,7 @@
     buckets[i] = new bucket[ncpus];
     for (unsigned int j = 0; j < ncpus; j++) {
       // TODO dependency injection
-      size_t bucket_size = max((size_t) 1000000,buflen / ncpus * 3);
+      size_t bucket_size = max((size_t) min_bucket_size,buflen / ncpus * 3);
       // Each bucket should be twice as large as it would be given uniform
       // distribution. This is just an initial size; extending can happen.
       buckets[i][j].bufs.push_back(new char[bucket_size]);
@@ -260,7 +261,7 @@
 {
   size_t h = hash_djb2(s);
   unsigned int bucket = h % ncpus;
-  size_t bucket_size = max((size_t) 1000000, buflen * 3 / ncpus);
+  size_t bucket_size = max((size_t) min_bucket_size, buflen * 3 / ncpus);
   if (heads[bucket] + nbytes < bs[bucket].bufs.back() + bucket_size) {
     memcpy(heads[bucket], p, nbytes);
     heads[bucket] += nbytes;
@@ -470,7 +471,7 @@
       }
     }
   }
-  cout << "cpu " << pid << " hits " << hits << " misses " << misses << endl;
+  // cout << "cpu " << pid << " hits " << hits << " misses " << misses << endl;
 }
 
 // vim:et:sw=2:ts=2


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted: [394] numa-bench/trunk/src

[<yan...@us...>]

Revision: 394
          http://assorted.svn.sourceforge.net/assorted/?rev=394&view=rev
Author:   yangzhang
Date:     2008-02-12 11:16:18 -0800 (Tue, 12 Feb 2008)

Log Message:
-----------
added custom_alloc test

Modified Paths:
--------------
    numa-bench/trunk/src/Makefile

Added Paths:
-----------
    numa-bench/trunk/src/custom_alloc.cc

Modified: numa-bench/trunk/src/Makefile
===================================================================
--- numa-bench/trunk/src/Makefile	2008-02-12 18:01:24 UTC (rev 393)
+++ numa-bench/trunk/src/Makefile	2008-02-12 19:16:18 UTC (rev 394)
@@ -16,6 +16,9 @@
 threads: threads.cc $(COMMONS)
 	$(CXX)
 
+custom_alloc: custom_alloc.cc
+	$(CXX)
+
 openmp: openmp.cc
 	$(CXX) -fopenmp
 

Added: numa-bench/trunk/src/custom_alloc.cc
===================================================================
--- numa-bench/trunk/src/custom_alloc.cc	                        (rev 0)
+++ numa-bench/trunk/src/custom_alloc.cc	2008-02-12 19:16:18 UTC (rev 394)
@@ -0,0 +1,60 @@
+// TODO: add in test of tbb allocator.
+
+#include <commons/region.h>
+#include <commons/time.h>
+#include <commons/boost/threads.h>
+#include <boost/bind.hpp>
+
+using namespace boost;
+using namespace commons;
+
+void
+f(region_alloc<int>* a, int count)
+{
+  timer t("region: ");
+  int* j = NULL;
+  for (int i = 0; i < count; i++) {
+    j = a->allocate(1);
+  }
+  t.print();
+  cout << j << endl;
+}
+
+void
+g(int count)
+{
+  timer t("new: ");
+  int* j = NULL;
+  for (int i = 0; i < count; i++) {
+    j = new int;
+  }
+  t.print();
+  cout << j << endl;
+}
+
+int
+main()
+{
+  int ncores = 16;
+  int count = 1000000;
+  pthread_t ts[ncores];
+
+  // This is much faster.
+  {
+    region_alloc<int> as[ncores];
+    for (int i = 0; i < ncores; i++) {
+      check((ts[i] = spawn(bind(f, &as[i], count))) != 0);
+    }
+    waitall(ts, ncores);
+  }
+
+  // This is much slower.
+  {
+    for (int i = 0; i < ncores; i++) {
+      check((ts[i] = spawn(bind(g, count))) != 0);
+    }
+    waitall(ts, ncores);
+  }
+
+  return 0;
+}


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted: [393] cpp-commons/trunk/src/commons

[<yan...@us...>]

Revision: 393
          http://assorted.svn.sourceforge.net/assorted/?rev=393&view=rev
Author:   yangzhang
Date:     2008-02-12 10:01:24 -0800 (Tue, 12 Feb 2008)

Log Message:
-----------
added some debug output

Modified Paths:
--------------
    cpp-commons/trunk/src/commons/check.h
    cpp-commons/trunk/src/commons/region.h

Modified: cpp-commons/trunk/src/commons/check.h
===================================================================
--- cpp-commons/trunk/src/commons/check.h	2008-02-12 18:01:17 UTC (rev 392)
+++ cpp-commons/trunk/src/commons/check.h	2008-02-12 18:01:24 UTC (rev 393)
@@ -42,8 +42,19 @@
    * evaluation of msg.
    */
 #define checkmsg(cond, msg) \
-    bool b = cond; \
-    if (!b) _check(b, (msg), __FILE__, __LINE__)
+    bool b__ = cond; \
+    if (!b__) _check(b__, (msg), __FILE__, __LINE__)
 
+// TODO: half-written
+#define checkmsgf(cond, msg, ...) \
+  do { \
+    bool b__ = cond; \
+    if (!b__) { \
+      char s__[4096]; \
+      snprintf(s, ); \
+      _check(b__, s__, __FILE__, __LINE__); \
+    } \
+  } while (0)
+
 #endif
 

Modified: cpp-commons/trunk/src/commons/region.h
===================================================================
--- cpp-commons/trunk/src/commons/region.h	2008-02-12 18:01:17 UTC (rev 392)
+++ cpp-commons/trunk/src/commons/region.h	2008-02-12 18:01:24 UTC (rev 393)
@@ -5,6 +5,10 @@
 
 #include <limits>
 
+// XXX: debug
+#include <set>
+#include <pthread.h>
+
 namespace commons
 {
 
@@ -39,6 +43,7 @@
     const size_t chunk_size;
     size_t top;
     int    refcount;
+    set<pthread_t> threads;
 
   public:
     mem_region() :
@@ -46,12 +51,13 @@
       top(0),
       refcount(0)
     {
+      cout << "created " << this << endl;
       chunks.push_back((chunk) {chunk_size, new char[chunk_size]});
     }
 
     ~mem_region()
     {
-      // cout << "deleting" << endl;
+      cout << "deleting" << endl;
       for (unsigned int i = 0; i < chunks.size(); i++) {
         delete [] chunks[i].data;
       }
@@ -62,13 +68,15 @@
 
     void *alloc_mem(size_t n)
     {
-      if (top + n > chunk_size) {
-        // chunks.push_back(new char[chunk_size]);
-	size_t sz = max(n, chunk_size);
-	chunks.push_back((chunk) {sz, new char[sz] });
+      pthread_t t = pthread_self();
+      if (threads.insert(t).second)
+        cout << this << " -- " << t << endl;
+
+      if (top + n > chunks.back().size) {
+        size_t sz = max(n, chunk_size);
+        chunks.push_back((chunk) {sz, new char[sz] });
         top = 0;
       }
-      // cout << "alloced" << endl;
       size_t old_top = top;
       top += n;
       return chunks.back().data + old_top;


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted: [392] cpp-commons/trunk/src/commons/files.h

[<yan...@us...>]

Revision: 392
          http://assorted.svn.sourceforge.net/assorted/?rev=392&view=rev
Author:   yangzhang
Date:     2008-02-12 10:01:17 -0800 (Tue, 12 Feb 2008)

Log Message:
-----------
fixed bug: omitting end of file

Modified Paths:
--------------
    cpp-commons/trunk/src/commons/files.h

Modified: cpp-commons/trunk/src/commons/files.h
===================================================================
--- cpp-commons/trunk/src/commons/files.h	2008-02-12 17:08:58 UTC (rev 391)
+++ cpp-commons/trunk/src/commons/files.h	2008-02-12 18:01:17 UTC (rev 392)
@@ -69,17 +69,19 @@
     char *buf = new char[len + 1];
     check(buf);
 
+    ssize_t status = pread(fd, buf, len, 0);
+    size_t nread = static_cast<size_t>(status);
+    check(status != -1 && nread == len);
+
     // TODO Use threads to pull data to the correct initial locations?
-    // XXX alignment bug: not necessarily reading the full file (omitting final
-    // null terminators can cause issues)
-    size_t chunk_len = len / ncpus;
-    for (unsigned int i = 0; i < ncpus; i++) {
-      int off = i *chunk_len;
-      ssize_t status = pread(fd, buf + off, chunk_len, off);
-      // We read the whole chunk or hit the end.
-      size_t nread = static_cast<size_t>(status);
-      check(status != -1 && (nread == chunk_len || off + nread == len));
-    }
+    // size_t chunk_len = len / ncpus;
+    // for (unsigned int i = 0; i < ncpus; i++) {
+    //   int off = i *chunk_len;
+    //   ssize_t status = pread(fd, buf + off, chunk_len, off);
+    //   // We read the whole chunk or hit the end.
+    //   size_t nread = static_cast<size_t>(status);
+    //   check(status != -1 && (nread == chunk_len || off + nread == len));
+    // }
 
     check(close(fd) == 0);
 


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted: [387] hash-join/trunk/src/hashjoin.cc

[<yan...@us...>]

Revision: 387
          http://assorted.svn.sourceforge.net/assorted/?rev=387&view=rev
Author:   yangzhang
Date:     2008-02-12 08:33:50 -0800 (Tue, 12 Feb 2008)

Log Message:
-----------
trying new allocator; fixed bucket_size type issues

Modified Paths:
--------------
    hash-join/trunk/src/hashjoin.cc

Modified: hash-join/trunk/src/hashjoin.cc
===================================================================
--- hash-join/trunk/src/hashjoin.cc	2008-02-12 01:47:59 UTC (rev 386)
+++ hash-join/trunk/src/hashjoin.cc	2008-02-12 16:33:50 UTC (rev 387)
@@ -16,6 +16,7 @@
 #include <commons/deque.h>
 #include <commons/files.h>
 #include <commons/hash.h>
+#include <commons/region.h>
 #include <commons/strings.h>
 #include <commons/threads.h>
 #include <commons/time.h>
@@ -31,7 +32,14 @@
 using namespace commons;
 // TODO: using namespace boost;
 
-typedef hash_map<const char*, const void*, hash<const char*>, eqstr> my_hash_map;
+typedef hash_map<
+  const char*,
+  const void*,
+  hash<const char*>,
+  eqstr,
+  region_alloc<int>
+> my_hash_map;
+
 class hmap : public my_hash_map
 {
 public:
@@ -216,7 +224,7 @@
     buckets[i] = new bucket[ncpus];
     for (unsigned int j = 0; j < ncpus; j++) {
       // TODO dependency injection
-      size_t bucket_size = max(1000000U,buflen / ncpus * 3);
+      size_t bucket_size = max((size_t) 1000000,buflen / ncpus * 3);
       // Each bucket should be twice as large as it would be given uniform
       // distribution. This is just an initial size; extending can happen.
       buckets[i][j].bufs.push_back(new char[bucket_size]);
@@ -252,7 +260,7 @@
 {
   size_t h = hash_djb2(s);
   unsigned int bucket = h % ncpus;
-  size_t bucket_size = max(1000000U, buflen * 3 / ncpus);
+  size_t bucket_size = max((size_t) 1000000, buflen * 3 / ncpus);
   if (heads[bucket] + nbytes < bs[bucket].bufs.back() + bucket_size) {
     memcpy(heads[bucket], p, nbytes);
     heads[bucket] += nbytes;


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted: [389] cpp-commons/trunk/src/commons

[<yan...@us...>]

Revision: 389
          http://assorted.svn.sourceforge.net/assorted/?rev=389&view=rev
Author:   yangzhang
Date:     2008-02-12 08:35:02 -0800 (Tue, 12 Feb 2008)

Log Message:
-----------
fixed header ifndefs to avoid reserved symbols

Modified Paths:
--------------
    cpp-commons/trunk/src/commons/boost/threads.h
    cpp-commons/trunk/src/commons/check.h
    cpp-commons/trunk/src/commons/cpuid.h
    cpp-commons/trunk/src/commons/deque.h
    cpp-commons/trunk/src/commons/files.h
    cpp-commons/trunk/src/commons/hash.h
    cpp-commons/trunk/src/commons/strings.h
    cpp-commons/trunk/src/commons/threads.h
    cpp-commons/trunk/src/commons/time.h
    cpp-commons/trunk/src/commons/x86asm.h

Modified: cpp-commons/trunk/src/commons/boost/threads.h
===================================================================
--- cpp-commons/trunk/src/commons/boost/threads.h	2008-02-12 16:34:43 UTC (rev 388)
+++ cpp-commons/trunk/src/commons/boost/threads.h	2008-02-12 16:35:02 UTC (rev 389)
@@ -1,5 +1,5 @@
-#ifndef _COMMONS_BOOST_THREADS_H
-#define _COMMONS_BOOST_THREADS_H
+#ifndef COMMONS_BOOST_THREADS_H
+#define COMMONS_BOOST_THREADS_H
 
 #include <pthread.h>
 #include <sys/syscall.h>

Modified: cpp-commons/trunk/src/commons/check.h
===================================================================
--- cpp-commons/trunk/src/commons/check.h	2008-02-12 16:34:43 UTC (rev 388)
+++ cpp-commons/trunk/src/commons/check.h	2008-02-12 16:35:02 UTC (rev 389)
@@ -1,5 +1,5 @@
-#ifndef _COMMONS_CHECK_H
-#define _COMMONS_CHECK_H
+#ifndef COMMONS_CHECK_H
+#define COMMONS_CHECK_H
 
 #include <exception>
 #include <sstream>

Modified: cpp-commons/trunk/src/commons/cpuid.h
===================================================================
--- cpp-commons/trunk/src/commons/cpuid.h	2008-02-12 16:34:43 UTC (rev 388)
+++ cpp-commons/trunk/src/commons/cpuid.h	2008-02-12 16:35:02 UTC (rev 389)
@@ -3,8 +3,8 @@
 // spec.
 //
 
-#ifndef _COMMONS_CPUID_H
-#define _COMMONS_CPUID_H
+#ifndef COMMONS_CPUID_H
+#define COMMONS_CPUID_H
 
 #include <commons/x86asm.h>
 

Modified: cpp-commons/trunk/src/commons/deque.h
===================================================================
--- cpp-commons/trunk/src/commons/deque.h	2008-02-12 16:34:43 UTC (rev 388)
+++ cpp-commons/trunk/src/commons/deque.h	2008-02-12 16:35:02 UTC (rev 389)
@@ -1,5 +1,5 @@
-#ifndef _COMMONS_DEQUE_H
-#define _COMMONS_DEQUE_H
+#ifndef COMMONS_DEQUE_H
+#define COMMONS_DEQUE_H
 
 #include <list>
 #include <vector>

Modified: cpp-commons/trunk/src/commons/files.h
===================================================================
--- cpp-commons/trunk/src/commons/files.h	2008-02-12 16:34:43 UTC (rev 388)
+++ cpp-commons/trunk/src/commons/files.h	2008-02-12 16:35:02 UTC (rev 389)
@@ -1,5 +1,5 @@
-#ifndef _COMMONS_FILES_H
-#define _COMMONS_FILES_H
+#ifndef COMMONS_FILES_H
+#define COMMONS_FILES_H
 
 #include <exception>
 #include <fstream>

Modified: cpp-commons/trunk/src/commons/hash.h
===================================================================
--- cpp-commons/trunk/src/commons/hash.h	2008-02-12 16:34:43 UTC (rev 388)
+++ cpp-commons/trunk/src/commons/hash.h	2008-02-12 16:35:02 UTC (rev 389)
@@ -1,5 +1,5 @@
-#ifndef _COMMONS_HASH_H
-#define _COMMONS_HASH_H
+#ifndef COMMONS_HASH_H
+#define COMMONS_HASH_H
 
 #include <sys/types.h>
 

Modified: cpp-commons/trunk/src/commons/strings.h
===================================================================
--- cpp-commons/trunk/src/commons/strings.h	2008-02-12 16:34:43 UTC (rev 388)
+++ cpp-commons/trunk/src/commons/strings.h	2008-02-12 16:35:02 UTC (rev 389)
@@ -1,7 +1,7 @@
 // TODO: move whatever you can to C99 Commons
 
-#ifndef _COMMONS_STRINGS_H
-#define _COMMONS_STRINGS_H
+#ifndef COMMONS_STRINGS_H
+#define COMMONS_STRINGS_H
 
 #include <strings.h>
 

Modified: cpp-commons/trunk/src/commons/threads.h
===================================================================
--- cpp-commons/trunk/src/commons/threads.h	2008-02-12 16:34:43 UTC (rev 388)
+++ cpp-commons/trunk/src/commons/threads.h	2008-02-12 16:35:02 UTC (rev 389)
@@ -1,5 +1,5 @@
-#ifndef _COMMONS_THREADS_H
-#define _COMMONS_THREADS_H
+#ifndef COMMONS_THREADS_H
+#define COMMONS_THREADS_H
 
 #include <pthread.h>
 #include <sys/syscall.h>

Modified: cpp-commons/trunk/src/commons/time.h
===================================================================
--- cpp-commons/trunk/src/commons/time.h	2008-02-12 16:34:43 UTC (rev 388)
+++ cpp-commons/trunk/src/commons/time.h	2008-02-12 16:35:02 UTC (rev 389)
@@ -1,5 +1,5 @@
-#ifndef _COMMONS_TIME_H
-#define _COMMONS_TIME_H
+#ifndef COMMONS_TIME_H
+#define COMMONS_TIME_H
 
 #include <string>
 #include <iostream>

Modified: cpp-commons/trunk/src/commons/x86asm.h
===================================================================
--- cpp-commons/trunk/src/commons/x86asm.h	2008-02-12 16:34:43 UTC (rev 388)
+++ cpp-commons/trunk/src/commons/x86asm.h	2008-02-12 16:35:02 UTC (rev 389)
@@ -1,5 +1,5 @@
-#ifndef _COMMONS_X86ASM_H
-#define _COMMONS_X86ASM_H
+#ifndef COMMONS_X86ASM_H
+#define COMMONS_X86ASM_H
 
 namespace commons
 {


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted: [391] cpp-commons/trunk/src/commons/region.h

[<yan...@us...>]

Revision: 391
          http://assorted.svn.sourceforge.net/assorted/?rev=391&view=rev
Author:   yangzhang
Date:     2008-02-12 09:08:58 -0800 (Tue, 12 Feb 2008)

Log Message:
-----------
added support for arbitrary-sized allocations

Modified Paths:
--------------
    cpp-commons/trunk/src/commons/region.h

Modified: cpp-commons/trunk/src/commons/region.h
===================================================================
--- cpp-commons/trunk/src/commons/region.h	2008-02-12 16:45:07 UTC (rev 390)
+++ cpp-commons/trunk/src/commons/region.h	2008-02-12 17:08:58 UTC (rev 391)
@@ -16,45 +16,62 @@
   const size_t default_chunk_size = 100000000;
 
   /**
+   * A fixed-size buffer (really just a pair of length and pointer).
+   */
+  struct chunk
+  {
+    size_t size;
+    char* data;
+  };
+
+  /**
    * Simple dynamically growing memory region that does not support
    * deallocation.
    */
   class mem_region
   {
   private:
-    vector<char*> chunks;
+    vector<chunk> chunks;
+    /**
+     * The default chunk-size when incrementally resizing; we can still handle
+     * larger allocations.
+     */
     const size_t chunk_size;
     size_t top;
-    int    m_refcount;
+    int    refcount;
 
   public:
     mem_region() :
       chunk_size(default_chunk_size),
       top(0),
-      m_refcount(0)
+      refcount(0)
     {
-      chunks.push_back(new char[chunk_size]);
+      chunks.push_back((chunk) {chunk_size, new char[chunk_size]});
     }
 
     ~mem_region()
     {
+      // cout << "deleting" << endl;
       for (unsigned int i = 0; i < chunks.size(); i++) {
-        delete [] chunks[i];
+        delete [] chunks[i].data;
       }
     }
 
-    void addref() { ++m_refcount; }
-    void decref() { if (--m_refcount == 0) { delete this; } }
+    void addref() { ++refcount; }
+    void decref() { if (--refcount == 0) { delete this; } }
 
     void *alloc_mem(size_t n)
     {
       if (top + n > chunk_size) {
-        chunks.push_back(new char[chunk_size]);
+        // chunks.push_back(new char[chunk_size]);
+	size_t sz = max(n, chunk_size);
+	chunks.push_back((chunk) {sz, new char[sz] });
         top = 0;
       }
+      // cout << "alloced" << endl;
       size_t old_top = top;
       top += n;
-      return chunks.back() + old_top;
+      return chunks.back().data + old_top;
     }
   };
 


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted: [390] cpp-commons/trunk/src/commons/region.h

[<yan...@us...>]

Revision: 390
          http://assorted.svn.sourceforge.net/assorted/?rev=390&view=rev
Author:   yangzhang
Date:     2008-02-12 08:45:07 -0800 (Tue, 12 Feb 2008)

Log Message:
-----------
implemented max_size

Modified Paths:
--------------
    cpp-commons/trunk/src/commons/region.h

Modified: cpp-commons/trunk/src/commons/region.h
===================================================================
--- cpp-commons/trunk/src/commons/region.h	2008-02-12 16:35:02 UTC (rev 389)
+++ cpp-commons/trunk/src/commons/region.h	2008-02-12 16:45:07 UTC (rev 390)
@@ -8,6 +8,8 @@
 namespace commons
 {
 
+  using namespace std;
+
   /**
    * Default chunk size is 100MB.
    */
@@ -121,10 +123,13 @@
     ~region_alloc() throw() { region->decref(); }
 
     /**
-     * Return maximum number of elements that can be allocated. Throws an
-     * exception.
+     * Return maximum number of elements that can be allocated. Simply return
+     * the size based on the size of memory.
      */
-    size_type max_size() const throw() { throw exception(); }
+    size_type max_size() const throw()
+    {
+      return numeric_limits<size_t>::max() / sizeof(T);
+    }
 
     /**
      * Allocate (but don't initialize) num elements of type T.


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted: [388] cpp-commons/trunk/src/commons/region.h

[<yan...@us...>]

Revision: 388
          http://assorted.svn.sourceforge.net/assorted/?rev=388&view=rev
Author:   yangzhang
Date:     2008-02-12 08:34:43 -0800 (Tue, 12 Feb 2008)

Log Message:
-----------
added region.h

Added Paths:
-----------
    cpp-commons/trunk/src/commons/region.h

Added: cpp-commons/trunk/src/commons/region.h
===================================================================
--- cpp-commons/trunk/src/commons/region.h	                        (rev 0)
+++ cpp-commons/trunk/src/commons/region.h	2008-02-12 16:34:43 UTC (rev 388)
@@ -0,0 +1,177 @@
+// TODO: use shared_ptr instead of custom ref counting?
+
+#ifndef COMMONS_REGION_H
+#define COMMONS_REGION_H
+
+#include <limits>
+
+namespace commons
+{
+
+  /**
+   * Default chunk size is 100MB.
+   */
+  const size_t default_chunk_size = 100000000;
+
+  /**
+   * Simple dynamically growing memory region that does not support
+   * deallocation.
+   */
+  class mem_region
+  {
+  private:
+    vector<char*> chunks;
+    const size_t chunk_size;
+    size_t top;
+    int    m_refcount;
+
+  public:
+    mem_region() :
+      chunk_size(default_chunk_size),
+      top(0),
+      m_refcount(0)
+    {
+      chunks.push_back(new char[chunk_size]);
+    }
+
+    ~mem_region()
+    {
+      for (unsigned int i = 0; i < chunks.size(); i++) {
+        delete [] chunks[i];
+      }
+    }
+
+    void addref() { ++m_refcount; }
+    void decref() { if (--m_refcount == 0) { delete this; } }
+
+    void *alloc_mem(size_t n)
+    {
+      if (top + n > chunk_size) {
+        chunks.push_back(new char[chunk_size]);
+        top = 0;
+      }
+      size_t old_top = top;
+      top += n;
+      return chunks.back() + old_top;
+    }
+  };
+
+  /**
+   * Standard region-based allocator. Useful for restricting locality and/or
+   * avoiding multithreaded contention.
+   */
+  template <class T>
+  class region_alloc {
+  public:
+    // Type definitions.
+    typedef T              value_type;
+    typedef T*             pointer;
+    typedef const T*       const_pointer;
+    typedef T&             reference;
+    typedef const T&       const_reference;
+    typedef std::size_t    size_type;
+    typedef std::ptrdiff_t difference_type;
+
+    typedef mem_region     pool_type;
+
+    /**
+     * Rebind allocator to type U.
+     */
+    template <class U>
+    struct rebind {
+      typedef region_alloc<U> other;
+    };
+
+    /**
+     * Return address of values.
+     */
+    pointer address (reference value) const { return &value; }
+    const_pointer address (const_reference value) const { return &value; }
+
+    /**
+     * Default constructor creates a new pool.
+     */
+    region_alloc() throw() {
+      region = new pool_type;
+      region->addref();
+    }
+
+    /**
+     * Copy constructor addrefs the region.
+     * TODO: This is in fact highly necessary. Understand why. Understand both
+     * the following ctors.
+     */
+    region_alloc(const region_alloc& src) throw() {
+      region = src.region;
+      region->addref();
+    }
+
+    /**
+     * Copy constructor addrefs the region.
+     */
+    template <class U>
+    region_alloc (const region_alloc<U> &src) throw() {
+      region = src.region;
+      region->addref();
+    }
+
+    /**
+     * Destructor decrefs the region.
+     */
+    ~region_alloc() throw() { region->decref(); }
+
+    /**
+     * Return maximum number of elements that can be allocated. Throws an
+     * exception.
+     */
+    size_type max_size() const throw() { throw exception(); }
+
+    /**
+     * Allocate (but don't initialize) num elements of type T.
+     */
+    pointer allocate(size_type num, const void* = 0)
+    {
+      return (pointer) region->alloc_mem(num * sizeof(T));
+    }
+
+    /**
+     * Initialize elements of allocated storage p with value `value` using
+     * placement new.
+     */
+    void construct(pointer p, const T& value) { new((void*)p)T(value); }
+
+    /**
+     * Destroy elements of initialized storage p by calling their destructor.
+     */
+    void destroy(pointer p) { p->~T(); }
+
+    /**
+     * Deallocate storage p of deleted elements. This actually does nothing.
+     */
+    void deallocate(pointer p, size_type num) {}
+
+    // TODO: why can't this be private? (cp ctor fails)
+    pool_type  *region;
+  };
+
+  /**
+   * All allocators of the same type are supposed to be equal.
+   * TODO: Understand why.
+   */
+  template <class T1, class T2>
+  bool operator== (const region_alloc<T1>&, const region_alloc<T2>&) throw() {
+    return true;
+  }
+
+  /**
+   * All allocators of the same type are supposed to be equal.
+   * TODO: Understand why.
+   */
+  template <class T1, class T2>
+  bool operator!= (const region_alloc<T1>&, const region_alloc<T2>&) throw() {
+    return false;
+  }
+
+}
+
+#endif


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted: [386] numa-bench/trunk/src/malloc.cc

[<yan...@us...>]

Revision: 386
          http://assorted.svn.sourceforge.net/assorted/?rev=386&view=rev
Author:   yangzhang
Date:     2008-02-11 17:47:59 -0800 (Mon, 11 Feb 2008)

Log Message:
-----------
nice malloc test

Modified Paths:
--------------
    numa-bench/trunk/src/malloc.cc

Modified: numa-bench/trunk/src/malloc.cc
===================================================================
--- numa-bench/trunk/src/malloc.cc	2008-02-12 01:22:31 UTC (rev 385)
+++ numa-bench/trunk/src/malloc.cc	2008-02-12 01:47:59 UTC (rev 386)
@@ -1,5 +1,22 @@
-// Does malloc tend to allocate locally?
+// Questions this program answers:
+//
+// - Does malloc tend to allocate locally?
+//   - Yes. Times working from local node is lower.
+// - How much does working from another node affect throughput?
+//   - A bit: 647x from local, 649x from neighbor, 651x from remote
+// - Is there difference from repeatedly fetching the same (large) area n times
+//   vs. fetching an area n times larger?
+//   - No. The times are identical for 1GB*1 and 100MB*10.
+// - How much difference is there between sequential scan and random access?
+//   - Huge difference. Also magnifies the locality effects more.
+//   - 1700 from local, 1990 from one neighbor, 2020 from another neighbor,
+//     and 2310 from remote.
+// - Can we observe prefetching's effects? (Random access but chew the full
+//   cache line of data.)
+//   - TODO!
 
+// TODO: use real shuffling? or is rand ok?
+
 #include <cstdlib>
 #include <iostream>
 
@@ -16,30 +33,44 @@
 using namespace commons;
 using namespace std;
 
-const size_t size = 10000000;
-
+/**
+ * \param pp The start of the buffer to chew.
+ * \param core Which core to pin our thread to.
+ * \param size The size of the buffer.
+ * \param nreps The number of times to chew through the buffer.
+ * \param shuffle If false, sequentially chew through; otherwise, randomly
+ *     shuffle the indexes we chew through.
+ */
 void*
-chew(void* pp, int core)
+chew(void* pp, int core, size_t size, int nreps, bool shuffle)
 {
   char* p = (char*) pp;
-  const int reps = 100;
   pid_t pid = gettid();
   timer t(": ");
 
-  // Pin this thread to the right processor.
+  // Pin this thread to core `core`.
   cpu_set_t cs;
   CPU_ZERO(&cs);
   CPU_SET(core, &cs);
   sched_setaffinity(pid, sizeof(cs), &cs);
 
-  for (int c = 0; c < reps; c++) {
-    for (size_t i = 0; i < size; i++) {
-      p[i] = i;
+  // Write sequentially to the memory region.
+  if (shuffle) {
+    for (int c = 0; c < nreps; c++) {
+      for (size_t i = 0; i < size; i++) {
+        p[rand() % size] = i;
+      }
     }
+  } else {
+    for (int c = 0; c < nreps; c++) {
+      for (size_t i = 0; i < size; i++) {
+        p[i] = i;
+      }
+    }
   }
 
   // Print the elapsed time.
-  cout << pid;
+  cout << core;
   t.print();
   return NULL;
 }
@@ -47,33 +78,31 @@
 int
 main(int argc, char** argv)
 {
-  if (argc < 2) {
-    cerr << "malloc <nthreads>" << endl;
+  if (argc < 5) {
+    cerr << argv[0] << " <ncores> <size> <nreps> <shuffle>" << endl;
     return 1;
   }
 
-  const int n = atoi(argv[1]);
+  // Parse command-line arguments.
+  const int ncores = atoi(argv[1]);
+  const size_t size = atoi(argv[2]);
+  const int nreps = atoi(argv[3]);
+  const bool shuffle = atoi(argv[4]);
+
   void *p = malloc(size);
 
-  // warmup
-  chew(p, 0);
-  pthread_t ts[n];
+  // Warmup.
+  cout << "warmup: ";
+  chew(p, 0, size, nreps, shuffle);
 
-  // start thread on each core
-  for (int i = 0; i < n; i++) {
+  // Chew the memory area from each core.
+  for (int i = 0; i < ncores; i++) {
     pthread_t t;
-    check((t = spawn(bind(chew, p, i))) != 0);
+    check((t = spawn(bind(chew, p, i, size, nreps, shuffle))) != 0);
     check(pthread_join(t, NULL) == 0);
   }
-  // waitall(ts, n);
-  return 0;
 
-  // THRASH
+  free(p);
 
-  // spawn workers
-  for (int i = 0; i < n; i++) {
-    check((ts[i] = spawn(bind(chew, p, i))) == 0);
-  }
-  waitall(ts, n);
   return 0;
 }


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted: [385] sandbox/trunk/src/cc/conversions.cc

[<yan...@us...>]

Revision: 385
          http://assorted.svn.sourceforge.net/assorted/?rev=385&view=rev
Author:   yangzhang
Date:     2008-02-11 17:22:31 -0800 (Mon, 11 Feb 2008)

Log Message:
-----------
added conversion test

Added Paths:
-----------
    sandbox/trunk/src/cc/conversions.cc

Added: sandbox/trunk/src/cc/conversions.cc
===================================================================
--- sandbox/trunk/src/cc/conversions.cc	                        (rev 0)
+++ sandbox/trunk/src/cc/conversions.cc	2008-02-12 01:22:31 UTC (rev 385)
@@ -0,0 +1,15 @@
+#include <iostream>
+
+using namespace std;
+
+int
+main()
+{
+  // This doesn't compile.
+  // int i("321");
+
+  // This doesn't work as expected; always outputs 1.
+  bool b("false");
+  cout << b << endl;
+}
+


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted: [384] hash-join/trunk/src/hashjoin.cc

[<yan...@us...>]

Revision: 384
          http://assorted.svn.sourceforge.net/assorted/?rev=384&view=rev
Author:   yangzhang
Date:     2008-02-11 15:31:10 -0800 (Mon, 11 Feb 2008)

Log Message:
-----------
fixed issues on 32-bit system

Modified Paths:
--------------
    hash-join/trunk/src/hashjoin.cc

Modified: hash-join/trunk/src/hashjoin.cc
===================================================================
--- hash-join/trunk/src/hashjoin.cc	2008-02-11 23:25:12 UTC (rev 383)
+++ hash-join/trunk/src/hashjoin.cc	2008-02-11 23:31:10 UTC (rev 384)
@@ -216,7 +216,7 @@
     buckets[i] = new bucket[ncpus];
     for (unsigned int j = 0; j < ncpus; j++) {
       // TODO dependency injection
-      size_t bucket_size = max(1000000UL,buflen / ncpus * 3);
+      size_t bucket_size = max(1000000U,buflen / ncpus * 3);
       // Each bucket should be twice as large as it would be given uniform
       // distribution. This is just an initial size; extending can happen.
       buckets[i][j].bufs.push_back(new char[bucket_size]);
@@ -252,7 +252,7 @@
 {
   size_t h = hash_djb2(s);
   unsigned int bucket = h % ncpus;
-  size_t bucket_size = max(1000000UL, buflen * 3 / ncpus);
+  size_t bucket_size = max(1000000U, buflen * 3 / ncpus);
   if (heads[bucket] + nbytes < bs[bucket].bufs.back() + bucket_size) {
     memcpy(heads[bucket], p, nbytes);
     heads[bucket] += nbytes;


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted: [383] cpp-commons/trunk/src/commons/strings.h

[<yan...@us...>]

Revision: 383
          http://assorted.svn.sourceforge.net/assorted/?rev=383&view=rev
Author:   yangzhang
Date:     2008-02-11 15:25:12 -0800 (Mon, 11 Feb 2008)

Log Message:
-----------
fixed crazy include

Modified Paths:
--------------
    cpp-commons/trunk/src/commons/strings.h

Modified: cpp-commons/trunk/src/commons/strings.h
===================================================================
--- cpp-commons/trunk/src/commons/strings.h	2008-02-11 23:23:55 UTC (rev 382)
+++ cpp-commons/trunk/src/commons/strings.h	2008-02-11 23:25:12 UTC (rev 383)
@@ -6,7 +6,6 @@
 #include <strings.h>
 
 #include <commons/check.h>
-#include <commons/pointers.h>
 
 namespace commons
 {


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted: [382] cpp-commons/trunk/src/commons/files.h

[<yan...@us...>]

Revision: 382
          http://assorted.svn.sourceforge.net/assorted/?rev=382&view=rev
Author:   yangzhang
Date:     2008-02-11 15:23:55 -0800 (Mon, 11 Feb 2008)

Log Message:
-----------
fixed casting bug

Modified Paths:
--------------
    cpp-commons/trunk/src/commons/files.h

Modified: cpp-commons/trunk/src/commons/files.h
===================================================================
--- cpp-commons/trunk/src/commons/files.h	2008-02-11 23:23:44 UTC (rev 381)
+++ cpp-commons/trunk/src/commons/files.h	2008-02-11 23:23:55 UTC (rev 382)
@@ -70,12 +70,14 @@
     check(buf);
 
     // TODO Use threads to pull data to the correct initial locations?
+    // XXX alignment bug: not necessarily reading the full file (omitting final
+    // null terminators can cause issues)
     size_t chunk_len = len / ncpus;
     for (unsigned int i = 0; i < ncpus; i++) {
       int off = i *chunk_len;
       ssize_t status = pread(fd, buf + off, chunk_len, off);
       // We read the whole chunk or hit the end.
-      size_t nread = static_cast<ssize_t>(status);
+      size_t nread = static_cast<size_t>(status);
       check(status != -1 && (nread == chunk_len || off + nread == len));
     }
 


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted: [381] cpp-commons/trunk/src/commons/strings.h

[<yan...@us...>]

Revision: 381
          http://assorted.svn.sourceforge.net/assorted/?rev=381&view=rev
Author:   yangzhang
Date:     2008-02-11 15:23:44 -0800 (Mon, 11 Feb 2008)

Log Message:
-----------
added scan

Modified Paths:
--------------
    cpp-commons/trunk/src/commons/strings.h

Modified: cpp-commons/trunk/src/commons/strings.h
===================================================================
--- cpp-commons/trunk/src/commons/strings.h	2008-02-11 23:23:00 UTC (rev 380)
+++ cpp-commons/trunk/src/commons/strings.h	2008-02-11 23:23:44 UTC (rev 381)
@@ -6,6 +6,7 @@
 #include <strings.h>
 
 #include <commons/check.h>
+#include <commons/pointers.h>
 
 namespace commons
 {
@@ -77,6 +78,60 @@
     return unsafe_strstr((char*) p, q, lim);
   }
 
+  /**
+   * "Touch" the entire memory region. Useful for ensuring that some piece of
+   * memory is "warmed up." Visits each character. Note that this might be
+   * optimized out if the caller doesn't meaningfully use the (mostly
+   * meaningless) return value.
+   */
+  inline char
+  scan(const void* buf, size_t len)
+  {
+    char sum = 0;
+    const char* start = (const char*) buf;
+    for (const char* p = start; p < start + len; p++) {
+      sum += *p;
+    }
+    return sum;
+  }
+
+  /**
+   * "Touch" the entire memory region. Useful for ensuring that some piece of
+   * memory is "warmed up." Uses memcpy on 1024-byte chunks. Note that this
+   * might be optimized out if the caller doesn't meaningfully use the (mostly
+   * meaningless) return value.
+   */
+  inline char
+  scan_big_step(const void* buf, size_t len)
+  {
+    const size_t sz = 1024;
+    char tmp[sz];
+    const char* p = (const char*) buf;
+    const char* end = p + len;
+    for (; p + sz < end; p += 1024) {
+      memcpy(tmp, p, sz);
+    }
+    memcpy(tmp, p, end - p);
+    return sz == 0 ? 0 : tmp[0];
+  }
+
+//  /**
+//   * Find an int in the buffer. Return pointer to the first occurrence on
+//   * success, NULL on failure.
+//   */
+//  inline const void*
+//  findint(const void* buf, size_t len, int x)
+//  {
+//    const void* pend = (buf + len);
+//    // Word-align the start and end pointers.
+//    const int* end = (const int*) round_up(p, sizeof(int));
+//    const int* start = (const int*) round_down(buf, sizeof(int));
+//    for (const int* p = buf; p < end; ++p) {
+//      if (*p == x) return p;
+//    }
+//    return NULL;
+//  }
+
 }
 
 #endif


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted: [380] hash-join/trunk/src/hashjoin.cc

[<yan...@us...>]

Revision: 380
          http://assorted.svn.sourceforge.net/assorted/?rev=380&view=rev
Author:   yangzhang
Date:     2008-02-11 15:23:00 -0800 (Mon, 11 Feb 2008)

Log Message:
-----------
added resize notices; fixed push_bucket

Modified Paths:
--------------
    hash-join/trunk/src/hashjoin.cc

Modified: hash-join/trunk/src/hashjoin.cc
===================================================================
--- hash-join/trunk/src/hashjoin.cc	2008-02-11 23:19:42 UTC (rev 379)
+++ hash-join/trunk/src/hashjoin.cc	2008-02-11 23:23:00 UTC (rev 380)
@@ -31,9 +31,20 @@
 using namespace commons;
 // TODO: using namespace boost;
 
+typedef hash_map<const char*, const void*, hash<const char*>, eqstr> my_hash_map;
+class hmap : public my_hash_map
+{
+public:
+  void
+  resize(size_type hint)
+  {
+    cout << "resizing " << this << " to " << hint << endl;
+    my_hash_map::resize(hint);
+  }
+};
+
 // TODO use dependency injection!
 unsigned int ncpus = 1;
-typedef hash_map<const char *, const void *, hash<const char *>, eqstr> hmap;
 const hmap::size_type map_size = 10000000;
 
 /**
@@ -68,7 +79,10 @@
 class db
 {
 public:
-  db(const char *path) : buf(load_file(path, buflen, ncpus)) {}
+  db(const char *path) : buf(load_file(path, buflen, ncpus))
+  {
+    scan(buf, buflen);
+  }
   /**
    * Run hash-partitioning phase on all processors.
    */
@@ -237,8 +251,8 @@
 db::push_bucket(char **heads, bucket *bs, const char *s, const char *p, size_t nbytes)
 {
   size_t h = hash_djb2(s);
-  unsigned int bucket = h % (map_size * ncpus) / map_size;
-  size_t bucket_size = max(1000000UL,buflen / ncpus * 3);
+  unsigned int bucket = h % ncpus;
+  size_t bucket_size = max(1000000UL, buflen * 3 / ncpus);
   if (heads[bucket] + nbytes < bs[bucket].bufs.back() + bucket_size) {
     memcpy(heads[bucket], p, nbytes);
     heads[bucket] += nbytes;
@@ -369,6 +383,7 @@
 movdb::build1(unsigned int pid, const bucket **movbucs, hmap *ph)
 {
   hmap &h = *ph;
+  h.resize(map_size);
   // Visit each bucket that's destined to us (visit each source).
   for (unsigned int i = 0; i < ncpus; i++) {
     const vector<char*>& bufs = movbucs[i][pid].bufs;
@@ -434,7 +449,7 @@
             hits++;
             join(title, name);
           } else {
-	    if (misses == 0) cerr << "MISS: '" << title << '\'' << endl;
+            if (misses == 0) cerr << "MISS: '" << title << '\'' << endl;
             misses++;
           }
           // End of a tuple? (Don't actually need this check, since the


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted: [379] hash-join/trunk/README

[<yan...@us...>]

Revision: 379
          http://assorted.svn.sourceforge.net/assorted/?rev=379&view=rev
Author:   yangzhang
Date:     2008-02-11 15:19:42 -0800 (Mon, 11 Feb 2008)

Log Message:
-----------
more informative readme

Modified Paths:
--------------
    hash-join/trunk/README

Modified: hash-join/trunk/README
===================================================================
--- hash-join/trunk/README	2008-02-11 23:11:38 UTC (rev 378)
+++ hash-join/trunk/README	2008-02-11 23:19:42 UTC (rev 379)
@@ -1,3 +1,9 @@
+% Parallel Hash Join
+% Yang Zhang
+
+Overview
+--------
+
 This is a simple implementation of parallel hash joins. I'm using this as a
 first step in studying the performance problems in multicore systems
 programming. This implementation is tailored for a particular dataset, the IMDB
@@ -3,11 +9,31 @@
 `movies.list` and `actresses.list` files, which may be found [here].
 
-The `tools/` directory contains `DbPrep.scala`, which is a filter for the
-`.list` files to prepare them to be more easily parsed by the hash join
-application.
+Requirements
+------------
 
-The `tools/` directory also contains `LogProc.scala`, which processes stdout
-concatenated from multiple runs of the program. This will produce the time and
-speedup plots illustrating the scalability of the system.
+- [C++ Commons] svn r370+
+- [libstdc++] v4.1
 
+Supporting Tools
+----------------
+
+`DbPrep` filters the `.list` files to prepare them to be parsed by the hash
+join.
+
+`LogProc` processes stdout concatenated from multiple runs of the program. This
+will produce the time and speedup plots illustrating the scalability of the
+system. This has actually been made into a generic tool and will be moved to
+its own project directory later.
+
+`Titles` extracts the titles from the output of `DbPrep` on `movies.list`.
+
+Related
+-------
+
+I used [HashDist] to experiment with the chaining of various hash functions on
+this dataset and observe the distribution.
+
 [here]: http://us.imdb.com/interfaces#plain
+[libstdc++]: http://gcc.gnu.org/libstdc++/
+[C++ Commons]: http://assorted.sf.net/
+[HashDist]: http://assorted.sf.net/


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted: [378] hash-join/trunk/tools

[<yan...@us...>]

Revision: 378
          http://assorted.svn.sourceforge.net/assorted/?rev=378&view=rev
Author:   yangzhang
Date:     2008-02-11 15:11:38 -0800 (Mon, 11 Feb 2008)

Log Message:
-----------
tweaks

Modified Paths:
--------------
    hash-join/trunk/tools/DbPrep.scala
    hash-join/trunk/tools/Titles.scala

Modified: hash-join/trunk/tools/DbPrep.scala
===================================================================
--- hash-join/trunk/tools/DbPrep.scala	2008-02-11 17:03:34 UTC (rev 377)
+++ hash-join/trunk/tools/DbPrep.scala	2008-02-11 23:11:38 UTC (rev 378)
@@ -10,7 +10,7 @@
   }
   def cleanTitle(line: String) = {
     val t = line indexOf "  "
-    if (t > 0) line take t else line
+    if (t > 0) line take t mkString else line
   }
   def main(args: Array[String]) {
     val pMovie = Pattern compile """^([^\t]+)\t+(.*)$"""

Modified: hash-join/trunk/tools/Titles.scala
===================================================================
--- hash-join/trunk/tools/Titles.scala	2008-02-11 17:03:34 UTC (rev 377)
+++ hash-join/trunk/tools/Titles.scala	2008-02-11 23:11:38 UTC (rev 378)
@@ -3,7 +3,7 @@
   def main(args: Array[String]) {
     var newPar = true
     for (line <- untilNull(Console.readLine)) {
-      if (newPar) {
+      if (!(line isEmpty) && newPar) {
         println(line)
         newPar = false
       }


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.