Reply to topic  [ 6 posts ] 
Oxy groups versus Yeti hashes 
Author Message
Yorick Master

Joined: Wed Jun 01, 2005 11:34 am
Posts: 112
Post Oxy groups versus Yeti hashes
I was curious to see whether oxy groups worked faster than Yeti hashes, and to my surprise, I discovered that they seem to be slower. Here is the test code I used:

Code:
func test_create_hash(count) {
   temp = h_new();
   for(i = 1; i <= count; i++)
      h_set, temp, swrite(format="item_%d", i), -1;
   return temp;
}

func test_create_obj(count) {
   temp = save();
   for(i = 1; i <= count; i++)
      save, temp, swrite(format="item_%d", i), -1;
   return temp;
}

func test_create(iters, items) {
   t0 = array(double, 3);
   timer, t0;
   for(i = 1; i <= iters; i++)
      test_create_hash, items;
   timer_finished, t0, fmt="Yeti hash: SECONDS\n";
   timer, t0;
   for(i = 1; i <= iters; i++)
      test_create_obj, items;
   timer_finished, t0, fmt="Oxy group: SECONDS\n";
}

func test_lookup_obj(obj, step, count) {
   for(i = 1; i <= step; i++)
      for(j = i; j <= count; j += step)
         temp = obj(swrite(format="item_%d", j));
}

func test_lookup(iters, items, step) {
   t0 = array(double, 3);
   temp = test_create_hash(items);
   timer, t0;
   for(i = 1; i <= iters; i++)
      test_lookup_obj, temp, step, items;
   timer_finished, t0, fmt="Yeti hash: SECONDS\n";
   temp = test_create_obj(items);
   timer, t0;
   for(i = 1; i <= iters; i++)
      test_lookup_obj, temp, step, items;
   timer_finished, t0, fmt="Oxy group: SECONDS\n";
}

func test_pop_hash(hash, step, count) {
   for(i = 1; i <= step; i++)
      for(j = i; j <= count; j += step)
         h_pop, hash, swrite(format="item_%d", j);
}

func obj_pop_item(&obj, item) {
   if(!obj(*)) return;
   keep = array(short(1), obj(*));
   if(obj(*,item))
      keep(obj(*,item)) = 0;
   w = where(keep);
   obj = numberof(w) ? obj(noop(w)) : save();
}

func test_pop_obj(obj, step, count) {
   for(i = 1; i <= step; i++)
      for(j = i; j <= count; j += step)
         obj_pop_item, obj, swrite(format="item_%d", j);
}

func test_pop(iters, items, step) {
   t0 = array(double, 3);
   temp = test_create_hash(items);
   timer, t0;
   for(i = 1; i <= iters; i++)
      test_pop_hash, temp, step, items;
   timer_finished, t0, fmt="Yeti hash: SECONDS\n";
   temp = test_create_obj(items);
   timer, t0;
   for(i = 1; i <= iters; i++)
      test_pop_obj, temp, step, items;
   timer_finished, t0, fmt="Oxy group: SECONDS\n";
}


(Function "timer_finished" is just a wrapper around using timer to print out the time elapsed.)

Here's some output from it:

Code:
> test_create, 10000, 100
Yeti hash: 1.3283
Oxy group: 1.5567
> test_create, 100, 10000
Yeti hash: 1.3865
Oxy group: 2.6696
> test_create, 10, 100000
Yeti hash: 1.4160
Oxy group: 8.6174
> test_lookup, 1000, 1000, 37
Yeti hash: 1.2289
Oxy group: 1.4210
> test_lookup, 100, 10000, 37
Yeti hash: 1.2490
Oxy group: 2.0128
> test_lookup, 10, 100000, 37
Yeti hash: 1.2926
Oxy group: 5.3700
> test_pop, 1000, 100, 37
Yeti hash: 0.1328
Oxy group: 1.1747
> test_pop, 100, 1000, 37
Yeti hash: 0.1317
Oxy group: 6.4145


So it appears that Yeti is much faster at adding and retrieving, and scales much better as the count goes up. Yeti notably also includes one major feature that I wish was present for oxy groups: h_pop and h_delete, which allow you to delete items from the hash. For oxy groups, you can't delete. You have to create a new item that lacks the items you want to drop. Because of this, the performance for removing items from an oxy group is abysmal. (Unless there's a better way to do it than the one I'm using?)

Thus I have two sets of questions.

1. Is this performance behavior expected? The oxy groups have a lot more functionality tied into them, so I can see why there'd be a bit more overhead. But I was surprised to see how poorly they scaled when working with lots of items.

2. If Yeti hashes work for a particular problem, is it recommended to continue using them? Will they continue to be developed and supported? Or should we be using oxy groups instead of Yeti hashes in future code, since oxy groups effectively cover the same functionality?


Tue Dec 21, 2010 11:58 am
Profile
Yorick Guru

Joined: Wed Nov 24, 2004 12:51 pm
Posts: 97
Location: Observatoire de Lyon (France)
Post 
I have slightly modified your code to:
* pre-create the item names to speedup and not count the time for each swrite
* re-create objects/hashes after popping all items to avoid popping an empty object/hash for the subsequent operations
* provide a fast pop operation for objects which just redefine the member to be empty if it exists
* fix the behiavior of your obj_pop_item
* write more informative title
* provide a replacement for your missing timer_finished function[/list]
The new code is:
Code:
func test_create_hash(items) {
  count = numberof(items);
  temp = h_new();
  for(i = 1; i <= count; ++i)
    h_set, temp, items(i), -1;
  return temp;
}

func test_create_obj(items) {
  count = numberof(items);
  temp = save();
  for(i = 1; i <= count; ++i)
    save, temp, items(i), -1;
  return temp;
}

func test_create(iters, nitems) {
  items = swrite(format="item_%d", indgen(nitems));
  write, format="CREATE (%d items x %d times)\n", nitems, iters;
  t0 = array(double, 3);
  timer, t0;
  for(i = 1; i <= iters; ++i)
    test_create_hash, items;
  timer_finished, t0, fmt=" - Yeti hash: SECONDS\n";
  timer, t0;
  for(i = 1; i <= iters; ++i)
    test_create_obj, items;
  timer_finished, t0, fmt=" - Oxy group: SECONDS\n";
}

func test_lookup_obj(obj, step, items) {
  count = numberof(items);
  for(i = 1; i <= step; ++i)
    for(j = i; j <= count; j += step)
      temp = obj(swrite(format="item_%d", j));
}

func test_lookup(iters, nitems, step) {
  items = swrite(format="item_%d", indgen(nitems));
  write, format="LOOKUP (%d items by step of %d x %d times)\n",
    nitems, step, iters;
  t0 = array(double, 3);
  temp = test_create_hash(items);
  timer, t0;
  for(i = 1; i <= iters; ++i)
    test_lookup_obj, temp, step, items;
  timer_finished, t0, fmt=" - Yeti hash: SECONDS\n";
  temp = test_create_obj(items);
  timer, t0;
  for(i = 1; i <= iters; ++i)
    test_lookup_obj, temp, step, items;
  timer_finished, t0, fmt=" - Oxy group: SECONDS\n";
}

func test_pop_hash(hash, step, items) {
  count = numberof(items);
  for(i = 1; i <= step; ++i)
    for(j = i; j <= count; j += step)
      h_pop, hash, items(j);
}

func obj_pop_item(&obj, item) {
  if (is_obj(obj,noop(item),1) >= 0) {
    index = obj(*,item);
    temp = obj(noop(index));
    (keep = array(int(1), obj(*)))(index) = 0;
    w = where(keep);
    obj = is_array(w) ? obj(noop(w)) : save();
    return temp;
  }
}

func test_pop_obj(obj, step, items) {
  count = numberof(items);
  for(i = 1; i <= step; ++i)
    for(j = i; j <= count; j += step)
      obj_pop_item, obj, items(j);
}

func obj_delete_item(obj, item) {
  if (is_obj(obj,noop(item),1) >= 0) {
    save, obj, noop(item), [];
  }
}

func test_delete_obj(obj, step, items) {
  count = numberof(items);
  for(i = 1; i <= step; ++i)
    for(j = i; j <= count; j += step)
      obj_delete_item, obj, items(j);
}

func test_pop(iters, nitems, step) {
  items = swrite(format="item_%d", indgen(nitems));
  write, format="POP (%d items by step of %d x %d times)\n",
    nitems, step, iters;
  t0 = array(double, 3);
  timer, t0;
  for(i = 1; i <= iters; ++i) {
    temp = test_create_hash(items);
    test_pop_hash, temp, step, items;
  }
  timer_finished, t0, fmt=" - Yeti hash: SECONDS\n";
  timer, t0;
  for(i = 1; i <= iters; ++i) {
    temp = test_create_obj(items);
    test_pop_obj, temp, step, items;
  }
  timer_finished, t0, fmt=" - Oxy group: SECONDS\n";
  timer, t0;
  for(i = 1; i <= iters; ++i) {
    temp = test_create_obj(items);
    test_delete_obj, temp, step, items;
  }
  timer_finished, t0, fmt=" - Oxy group (delete): SECONDS\n";
}
func timer_finished(t0, fmt=)
{
  t1 = t0;
  timer, t1;
  sec = swrite(format="%G", t1(3) - t0(3));
  if (is_void(fmt)) fmt = "Total time: SECONDS\n";
  sel = strfind("SECONDS", fmt);
  if (sel(2) >= 0) {
    str = streplace(fmt, sel, sec);
  } else {
    str = fmt + " " + sec + "\n";
  }
  write, format="%s", str;
}

test_create, 10000, 100;
test_create, 100, 10000;
test_create, 10, 100000;
test_lookup, 1000, 1000, 37;
test_lookup, 100, 10000, 37;
test_lookup, 10, 100000, 37;
test_pop, 1000, 100, 37;
test_pop, 100, 1000, 37;
and the results are (in brackets the timings on my machine with your version):
Code:
CREATE (100 items x 10000 times)
- Yeti hash: 0.338519                [0.818443]
- Oxy group: 0.455584                [0.92555 ]
CREATE (10000 items x 100 times)
- Yeti hash: 0.363644                [0.83402]
- Oxy group: 1.04653                 [1.5015]
CREATE (100000 items x 10 times)
- Yeti hash: 0.425294                [0.888353]
- Oxy group: 4.96778                 [5.34835]
LOOKUP (1000 items by step of 37 x 1000 times)
- Yeti hash: 0.723778                [0.710738]
- Oxy group: 0.900701                [0.884169]
LOOKUP (10000 items by step of 37 x 100 times)
- Yeti hash: 0.750517                [0.735494]
- Oxy group: 1.29364                 [1.29394]
LOOKUP (100000 items by step of 37 x 10 times)
- Yeti hash: 0.775814                [0.771637]
- Oxy group: 4.44393                 [4.49341]
POP (100 items by step of 37 x 1000 times)
- Yeti hash: 0.0698168               [0.0761809]
- Oxy group: 0.759472                [0.76702]
- Oxy group (delete): 0.149511
POP (1000 items by step of 37 x 100 times)
- Yeti hash: 0.066299                [0.0701952]
- Oxy group: 4.00608                 [4.02036]
- Oxy group (delete): 0.164311


Now to answer your questions:

* Yeti hash was developed with speed in mind so I expected it to be faster than Oxy group.

* The pop operation should be hard coded in Oxy to avoid re-creating the object, which explains the slowness of this operation in Oxy (consider using the alternative: replace the member by [] instead of really popping the member, which is not quite the same thing as the memeber would still exists but with an empty value).

* However, Oxy objects also use a hash-table so (apart for the pop operation) I cannot explain why their behavior scale so badly with the number of objects. We shall discuss with Dave to fix this issue.

* Yeti hash tables are heavily used in lot of shared software that we (in my team) and others have developped. So I will keep maintaining/improving them.


Wed Dec 22, 2010 7:16 am
Profile WWW
Yorick Guru

Joined: Sat Jan 22, 2005 2:44 pm
Posts: 86
Location: Pasadena, CA
Post Yeti-Oxy
Thank you for bringing this up, very interesting. I have been using yeti hash tables, both as containers and as objects, but I rarely have more than a few hundred members. I should migrate to Oxy, for portability sake.. but it will probably a while since yeti does the job perfectly.


Wed Dec 22, 2010 10:38 am
Profile YIM
Yorick Master

Joined: Mon Nov 22, 2004 9:43 am
Posts: 354
Location: Livermore, CA, USA
Post 
I am still studying this problem. The worrisome thing is the apparently poor scaling with the hash table size. The most likely culprit is the very questionable hash table implementation in the yorick global symbol table.

I built a profiling version of yorick to study the issue (-g -O0 -pg). The function which scales badly is HashFind, the yorick globtab lookup function, but I do not yet understand why. I rewrote the test program (given below) to better isolate the problems for profiling and timing. Although I can duplicate the poor scaling of of the original test program using my rewrite, a significant part of the poor scaling appears to be related to the near-duplicate sequence of names "item_0001", "item_0002", and so on. When I use random names, the globtab hashing does considerably better, arguably not scaling worse than the yeti tables (although as expected, the yeti dedicated hash tables are always going to be faster). I'm surprised the globtab hash function is so weak, but it is not impossible. If that is the problem, I'll look into whether it is possible to upgrade to a better hash algorithm (like the one in yeti).

A note for Eric: Yeti does not build (or no longer builds) with "make TGT=exe" -- I had to do some surgery to prepare a non-plugin version for profiling.

I do not believe that the oxy group obsoletes the yeti hash tables. The best way to bring the two things together is to redo the top layer of yeti/yeti_hash.c so that the hash table is an oxy object, analogous to the oxy group object. That way, the hash table would inherit all of its interface from the nearly identical oxy object interface. This would preserve most, but not all, of its current interface. As a bonus, you could use save and restore to insert and extract things from the yeti hash tables. There's no great rush to do this, and I haven't checked to see whether anything important gets lost or changed. It ought to considerably reduce the size of the yeti_hash.c source code, but I haven't checked that either.

Code:
/* testhash.i
* compares yeti hash tables with oxy group objects
* - yeti hash tables are power of two size open tables using Tcl hash
* - oxy groups use yorick global symbol table (globtab) to store name,
*   second integer hash table in group object to store globtab index
*   - globtab hashing is old and poorly implemented, uses prime table
*     size and questionable hash function
* hence yeti tables are expected to outperform oxy
* however, both should scale to larger table sizes as size*log(size)
*   to create the table, with time per lookup independent of size
* - failure to scale most likely indicates a poor hash function with
*   unexpectedly many collisions
*/

func setup(n, nit, regular)
{
  extern nitems, niters, iname, jname;
  nitems = n;
  niters = nit;
  if (regular) {
    /* original regular sequence of names and lookup order */
    iname = jname = swrite(format="item_%d", indgen(nitems));
    step = 37;
    for (i=k=1 ; i<=step ; ++i)
      for (j=i ; j<=nitems ; j+=step) jname(k++) = iname(j);
  } else {
    iname = *pointer("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_"+
                     "abcdefghijklmnopqrstuvwxyz");
    len = min(2 + long(abs(random_n(nitems)*2.5+3)), 10) + 1;
    len = len(cum);
    jname = 1+long(63*random(len(0)));
    jname(len(2:)) = 64; /* trailing \0 added at random name lengths */
    list = where(jname(1+len(:-1)) <= 10);
    if (numberof(list)) jname(1+len(list)) = 37; /* leading [0-9] becomes _ */
    /* use randomly generated names, and random permutation thereof */
    iname = strchar(iname(jname));
    jname = iname(sort(random(numberof(iname))));
  }

  /* final step is to generate global symbol table entry for every name
   * this prevents creation in global symtab from being counted against
   * oxy in later timings, and penalizes yeti so that the global creation
   * shows up in yeti profiling to facilitate comparison with oxy
   */
  treset;
  timer, ttot;
  for (i=1 ; i<=numberof(iname) ; ++i) symbol_set, iname(i), [];
  timer, ttot, tinit;
}

func treset
{
  extern tyeti, toxy, ttot, tinit;
  tyeti = toxy = ttot = tinit = array(0., 3);
}

func tprint(i)
{
  if (!i) i = 0;
  i = [" create", " lookup", " pop", ""](i);
  timer_print, "yeti"+i, tyeti, "oxy"+i, toxy, "setup global symtab", tinit;
}

func yi_create(time)
{
  if (time) timer, ttot;
  tmp = h_new();
  for (j=1 ; j<=nitems ; ++j) h_set, tmp, iname(j), -1;
  if (time) timer, ttot, tyeti;
  return tmp;
}

func oy_create(time)
{
  if (time) timer, ttot;
  tmp = save();
  for (j=1 ; j<=nitems ; ++j) save, tmp, iname(j), -1;
  if (time) timer, ttot, toxy;
  return tmp;
}

func docreate
{
  tyeti() = toxy() = 0.0;
  for (i=1 ; i<=niters ; ++i) {
    yi_create, 1;
    timer, ttot, tyeti;  /* adds time to destroy yeti hash */
  }
  for (i=1 ; i<=niters ; ++i)  {
    oy_create, 1;
    timer, ttot, toxy;  /* adds time to destroy oxy object */
  }
  tprint, 1;
}

func dolookup
{
  yeti = yi_create();
  oxy = oy_create();
  tyeti() = toxy() = 0.0;
  for (i=1 ; i<=niters ; ++i) {
    timer, ttot;
    for (j=1 ; j<=nitems ; ++j) tmp = yeti(jname(j));
    timer, ttot, tyeti;
  }
  for (i=1 ; i<=niters ; ++i)  {
    timer, ttot;
    for (j=1 ; j<=nitems ; ++j) tmp = oxy(jname(j));
    timer, ttot, toxy;
  }
  tprint, 2;
}


Fri Dec 24, 2010 5:14 pm
Profile
Yorick Guru

Joined: Wed Nov 24, 2004 12:51 pm
Posts: 97
Location: Observatoire de Lyon (France)
Post 
I agree that it would be a good idea to have hash table objects inherit the capabilities of Oxy objects.

Note to Dave: can you send me what you had to do to build a non-plugin version of Yeti so that I can modify Yeti?


Mon Dec 27, 2010 1:21 am
Profile WWW
Yorick Master

Joined: Wed Jun 01, 2005 11:34 am
Posts: 112
Post Re: Oxy groups versus Yeti hashes
I just wanted to give this a mild bump. I re-ran the test code as modified by Thiébaut and see that oxy groups still have some performance issues compared to Yeti, at least on the Yorick build I'm using (which is pretty recent). Has there been any further work on this?


Mon Feb 13, 2012 11:43 pm
Profile
Display posts from previous:  Sort by  
Reply to topic   [ 6 posts ] 

Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by STSoftware for PTF.