From: "Shot (Piotr Szotkowski)" <shot@...>
Date: 2009-11-17T06:06:51+09:00
Subject: Re: Looking for Set implementation in C

--yrj/dFKFPuw6o+aM
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

Robert Klemme:

> 2009/11/16 Shot (Piotr Szotkowski) <shot@hot.pl>:

>> The Set class in MRI is implemented in pure Ruby (lib/set.rb). I vaguely
>> remember someone posting here a C (re)implementation of the class, but
>> I can=E2=80=99t remember the details and it=E2=80=99s hard to google it =
=E2=80=93 all I could
>> find is the [ruby-talk:24465] thread.

> Why do you need that? Do you encounter any performance issues
> in the adapter code to Hash (which is implemented in C)?

My initial performance tests (with the very nice perftools.rb gem from
Aman Gupta) seem to suggest that I spend most of the time in (C-based)
Hash#each_key, mostly due to calls from Set#each =E2=80=93 but it looks like
the Set#each calls themselves add a significant overhead. Thus, I was
thinking that maybe a Set class which does not do additional Ruby calls,
but is itself implemented in C, might be faster.

Also, I just surprisingly discovered that
if I want to have Set#pairs such that

Set[1,2,3,4].pairs.to_a # =3D> [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

then doing

module Enumerable
  def pairs
    return combination 2 if respond_to? :combination
    Enumerator.new do |yielder|
      each_with_index do |a, i|
        each_with_index do |b, j|
          yielder.yield a, b if i < j
        end
      end
    end
  end
end

is actually much slower than the simple

module Enumerable
  def pairs
    combination 2
  end
end

class Set
  def pairs
    to_a.pairs
  end
end

which both surprises me a bit (I assumed the short lived Array creation
was expensive) and strenghtens my suspicions that the Ruby-based
Set class is rather slow and/or Array#combination=E2=80=99s Enumerator
initialisation is much faster (but, again, maybe because
Array#combination is written in C).

This, in turn, made me think that given that most of the core of my code
consists of operations on frozen Sets of Integers (usually Bignums),
then maybe a custom class for them (eventually most probably ported to
C or D) would make a lot of sense. As my C-fu is still somewhere between
rusty-beyond-all-hope and nonexistent, I=E2=80=99m looking for a Set in C so
that I can learn how it=E2=80=99s done =E2=80=93 although I should probably=
 just look
closely at hash.c, maybe with some ruby2c translation of set.rb to
speed-up my understanding of Ruby=E2=80=99s C interface.

Of course, the custom (immutable) class might also have the benefit of
caching the #pairs=E2=80=99 result, or at least its #to_a Array counterpart.

(For some reason I was also assuming that a custom IntSet class would
side-step the need for backporting r22308=C2=B9 to all my Ruby installs;
I then recalled that it fixes Bignum#hash, not Set#hash =E2=80=93 but now
I again think that if I build my custom IntSet class and am very
vigilant about not using Bignums in regular Sets or as Hash keys,
then I might really end up not needing the backport any more. I guess
redefining Bignum#hash to raise an exception would make a good guard
against this bug and show me how many places actually trigger it at the
moment.)

=C2=B9 http://redmine.ruby-lang.org/repositories/diff/ruby-19?rev=3D22308

=E2=80=94 Shot
--=20
No, no, it=E2=80=99s spelled Raymond Luxury Yacht,
but it=E2=80=99s pronounced Throatwobbler Mangrove.
                             [Monty Python]

--yrj/dFKFPuw6o+aM
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEARECAAYFAksBvuYACgkQi/mCfdEo8UponACgwSVIUfGqX3U4UoPgsqx8EPa7
uF8AoLXla4zC5LVdQuQ4AFimfTeUTrS9
=HzIs
-----END PGP SIGNATURE-----

--yrj/dFKFPuw6o+aM--