down with Set[Symbol]

[Miguel Garcia]

In the compiler, frequently a Set[Symbol] is used just for testing membership and adding symbols. In those cases, a Set[Int] containing symbol ids would equally do.

It's a low-hanging fruit that makes for lower GC.

Any disadvantages?


Miguel
http://lampwww.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/

[Miguel Garcia]

Just to clarify, in those cases where it's clear the Symbol are reachable and will stay so, e.g. via Trees.

Provided that's the case, Set[Symbol] as well as Maps with Symbol-keys; could use Int identities instead.


Miguel
http://lampwww.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/

[Rex Kerr]

If you don't have a set specialized on integers, couldn't that actually cause _more_ GC with all the boxing?  (More items to traverse.)

  --Rex

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Adriaan Moors]

Greg has done some work recently on making our hashconsing use WeakHashMaps. I guess similar optimizations await us for other big sets that are needlessly retained.

[Grzegorz Kossakowski]

On 28 February 2013 16:08, Adriaan Moors <adriaa...@typesafe.com> wrote:

Greg has done some work recently on making our hashconsing use WeakHashMaps. I guess similar optimizations await us for other big sets that are needlessly retained.

Documented here: https://issues.scala-lang.org/browse/SI-7149

--
Grzegorz Kossakowski

Scalac hacker at Typesafe

twitter: @gkossakowski

github: @gkossakowski

[Miguel Garcia]

To give an example:

  /** closures that are instantiated at least once, after dead code elimination */
  val liveClosures: mutable.Set[Symbol] = new mutable.HashSet()

The class-symbols added to that set are reachable via other means, the Set[Symbol] is used just to demarcate a subset of interest:

  for ((sym, cls) <- icodes.classes if inliner.isClosureClass(sym) && !deadCode.liveClosures(sym)) {
    . . .
  }


Miguel
http://lampwww.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/

[Matthew Pocock]

Is the compiler allowed to use tagged types? If Ints are being used as light-weight identifiers for Symbol, I'd want this documented and enforced by the type-system - things get cryptic really, really fast otherwise. Something like:

trait UniquelyIdentifies[T]

type SymbolId = Int with UniquelyIdentifies[Symbol]

This SymbolId type has a natural bijection to/from Symbol - wrap up the symbol id and resolve an id via a lookup function.

trait IdentityBijection[T, U] {

  def identify(u: U): T with UniquelyIdentifies[U]

  def resolve(t: T with UniquelyIdentifies[U]): U

}

I have no doubt that there are a bunch of places where this kind of thing goes on, with ints or strings or other structures acting as global or scoped identities for instances, and in many cases this won't be explicitly honoured in the types.

Matthew

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--

Dr Matthew Pocock

Integrative Bioinformatics Group, School of Computing Science, Newcastle University

mailto: turingate...@gmail.com

mailto: matthew...@ncl.ac.uk

gchat: turingate...@gmail.com

msn: matthew...@yahoo.co.uk

irc.freenode.net: drdozer

skype: matthew.pocock

tel: (0191) 2566550

mob: +447535664143

[Paul Phillips]

On Thu, Feb 28, 2013 at 3:58 PM, Rex Kerr <ich...@gmail.com> wrote:

If you don't have a set specialized on integers, couldn't that actually cause _more_ GC with all the boxing?  (More items to traverse.)

Yes, we would definitely need an IntSet, which we should have anyway. Doesn't have to be a "scala.collection.Set", either. For most uses it needs all of one method: contains.

[Paolo G. Giarrusso]

On Friday, March 1, 2013 9:33:02 AM UTC+9, Matthew Pocock wrote:

Is the compiler allowed to use tagged types? If Ints are being used as light-weight identifiers for Symbol, I'd want this documented and enforced by the type-system - things get cryptic really, really fast otherwise. Something like:

trait UniquelyIdentifies[T]

type SymbolId = Int with UniquelyIdentifies[Symbol]

This SymbolId type has a natural bijection to/from Symbol - wrap up the symbol id and resolve an id via a lookup function.

trait IdentityBijection[T, U] {

  def identify(u: U): T with UniquelyIdentifies[U]

  def resolve(t: T with UniquelyIdentifies[U]): U

}

I have no doubt that there are a bunch of places where this kind of thing goes on, with ints or strings or other structures acting as global or scoped identities for instances, and in many cases this won't be explicitly honoured in the types.

Matthew

 

Shouldn't value classes do the job here? In Haskell you're supposed to use newtype (if you want to avoid extra boxing), and value classes are supposed to be equivalent AFAIK. As in:

class SymbolId(val v: Int) extends AnyVal

or

case class SymbolId(v: Int) extends AnyVal

[Miguel Garcia]

Just to make more concrete the use case I had in mind, the supporting data structure that gets the job done can be seen here:
  https://github.com/magarciaEPFL/scala/commit/5442abbc670627fd6fdef654d7a9fd034e372946

And it's put to use here:
  https://github.com/magarciaEPFL/scala/commit/85122671bee09226349667e5dcb26d8b7357a6cc

Slightly different scenarios are thinkable, in the case at hand the above is a fine solution.

In case you spot other places in the compiler where the above can be put to use, please let us know!

Miguel
http://lampwww.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/

[Rex Kerr]

On Thu, Mar 28, 2013 at 2:09 PM, Paolo G. Giarrusso <p.gia...@gmail.com> wrote:

On Friday, March 1, 2013 9:33:02 AM UTC+9, Matthew Pocock wrote:

Is the compiler allowed to use tagged types? If Ints are being used as light-weight identifiers for Symbol, I'd want this documented and enforced by the type-system - things get cryptic really, really fast otherwise. Something like:

trait UniquelyIdentifies[T]

type SymbolId = Int with UniquelyIdentifies[Symbol]

This SymbolId type has a natural bijection to/from Symbol - wrap up the symbol id and resolve an id via a lookup function.

trait IdentityBijection[T, U] {

  def identify(u: U): T with UniquelyIdentifies[U]

  def resolve(t: T with UniquelyIdentifies[U]): U

}

I have no doubt that there are a bunch of places where this kind of thing goes on, with ints or strings or other structures acting as global or scoped identities for instances, and in many cases this won't be explicitly honoured in the types.

Matthew

 

Shouldn't value classes do the job here? In Haskell you're supposed to use newtype (if you want to avoid extra boxing), and value classes are supposed to be equivalent AFAIK. As in:

class SymbolId(val v: Int) extends AnyVal

or

case class SymbolId(v: Int) extends AnyVal

Sort of.  If you never store SymbolId in an array or use it in a specialized method (and want to avoid boxing), you're good.  Otherwise you need to revert it to Int while you're there and pack it back again when you pull it out.

I do this sort of thing all the time and it is a fair bit of a bookkeeping, so I (try to) only do it where it matters.

Since these things will be in some sort of collection, if it's a dedicated collection you can make sure it only takes/gives these faux-wrapped primitives.  Otherwise you'll have to wrap on the way in and out or box.

Also, this gives the JIT compiler a lot of unwrapping work to do since it generates a lot of methods that essentially do nothing (either literally, or can be trivially inlined).  (I am not sure how much this can be reduced by e.g. Miguel's new optimizer.)

  --Rex

[Miguel Garcia]

> Also, this gives the JIT compiler a lot of unwrapping work to do since it generates a lot of methods that essentially do nothing
> (either literally, or can be trivially inlined).  (I am not sure how much this can be reduced by e.g. Miguel's new optimizer.)

In case you have a "representative" example, please post it (here or in a new thread). I'll report then what the new optimizer does for the example.


Miguel
http://lampwww.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/

[Paolo Giarrusso]

You said Array, so can I have a Set[SymbolId] without problems,
assuming that Set doesn't use arrays of T?
Also, is there some documentation on these issues out there, for
unsuspecting Scala users like me?

Finally, this is rather sad. Is this a problem only because I have a
primitive inside the value class?

I mean, what you write suddenly means I'll have to be quite careful
with value classes, or maybe just not use them (or not as much as I'd
like). With all the type safety problems that Matthew described.

> Since these things will be in some sort of collection, if it's a dedicated
> collection you can make sure it only takes/gives these faux-wrapped
> primitives. Otherwise you'll have to wrap on the way in and out or box.

> Also, this gives the JIT compiler a lot of unwrapping work to do since it
> generates a lot of methods that essentially do nothing (either literally, or
> can be trivially inlined). (I am not sure how much this can be reduced by
> e.g. Miguel's new optimizer.)
--

Paolo G. Giarrusso - Ph.D. Student, Philipps-University Marburg
http://www.informatik.uni-marburg.de/~pgiarrusso/

[Rex Kerr]

Hopefully this is relevant enough to stay in the same thread.

The demands on the JIT compiler for value classes depends on how much you combine features.  It's really just the standard stuff from implicit conversions and case classes, except in this case the companion object apply and implicit conversions do literally nothing, so it's especially disappointing that they're there.

So given the code

class Valued(val repr: Int) extends AnyVal {
  def odd = (repr&1)==1
}

case class EasyVal(val repr: Int) extends AnyVal {
  def easy = this
  def even = (repr&1)==0
}

class Test {
  import language.implicitConversions
  implicit def reallyEasy(i: Int) = new EasyVal(i)

  def test = {
    val a = new Array[Int](1)

    val i = 7
    a(0) = i
    val j = a(0)

    val m = new Valued(8)
    a(0) = m.repr
    val n = new Valued(a(0))

    val p = EasyVal(9)
    a(0) = p.repr
    val q = a(0).easy

    (j,n,q)
  }
}

the relevant bits of bytecode for the integer, Valued, and EasyVal assign/save/load trio are, respectively:

// Int
   4:    bipush    7
   6:    istore_2
   7:    aload_1
   8:    iconst_0
   9:    iload_2
   10:    iastore
   11:    aload_1
   12:    iconst_0
   13:    iaload
   14:    istore_3

// Valued (value class of Int)
   15:    bipush    8
   17:    istore    4
   19:    aload_1
   20:    iconst_0
   21:    iload    4
   23:    iastore
   24:    aload_1
   25:    iconst_0
   26:    iaload
   27:    istore    5

// EasyVal (value class with bells and whistles)
   29:    bipush    9
   31:    istore    6
   33:    aload_1
   34:    iconst_0
   35:    iload    6
   37:    iastore
   38:    getstatic    #22; //Field EasyVal$.MODULE$:LEasyVal$;
   41:    aload_0
   42:    aload_1
   43:    iconst_0
   44:    iaload
   45:    invokevirtual    #24; //Method reallyEasy:(I)I
   48:    invokevirtual    #27; //Method EasyVal$.easy$extension:(I)I
   51:    istore    7

where the value class emits the same bytecode as the Int when undecorated, but emits do-nothing calls when you start decorating the value class to be easier to use.

If anything can be @inlined to improve things for the inliner, that's fine to add.  However, if it works on implicit def but not on implicit class, that's less useful (since I normally don't separate out the def like this).

  --Rex

[Rex Kerr]

Sorry, Array or generics.  Value classes, like primitives, are boxed.  Unlike primitives, you can't specialize on value classes.

Since Set[T] is generic, putting a value class in there is not likely to do what you want.  Nor is Set[Int], since the collections sets are not specialized.

Some customization is needed to get primitive-level performance.  If you

  class Symb(val id: Int) extends AnyVal {}

then you would when packing into arrays/specialized methods or whatever,

  a(i) = s.id
  val s2 = new Symb(a(j))

to store and retrieve the value.  If you do it this way there will be literally zero overhead in the bytecode; see my post to Miguel about wishing that the optimizer would remove the bytecode additions from handy utility methods that are really just the identity function under different names (but get called anyway--the JIT compiler will elide them, but why add bytecode just so the JIT can throw away your junk?).

  --Rex

[Paul Phillips]

On Thu, Mar 28, 2013 at 1:17 PM, Rex Kerr <ich...@gmail.com> wrote:

The demands on the JIT compiler for value classes depends on how much you combine features.  It's really just the standard stuff from implicit conversions and case classes, 

except in this case the companion object apply and implicit conversions do literally nothing, so it's especially disappointing that they're there.

 

When I looked into doing something about the "literally nothing" residue, I discovered it is not quite literally nothing, as explained in this comment from Predef. Strict adherence to language semantics means that you can't optimize away a call to a member of a companion object, ever, unless you can somehow prove it has already been loaded, because the call may cause it to be loaded, and its constructor may have side effects. This inhibits a huge range of potential optimizations. Some purity analysis will maybe help a lot, but it would still be a huge trap because the innocent addition of a single println to an object would be enough to give it a side-effecting constructor and again eliminate all optimization.

It would be easier and faster to do something about the language semantics.

  /** We prefer the java.lang.* boxed types to these wrappers in

   *  any potential conflicts.  Conflicts do exist because the wrappers

   *  need to implement ScalaNumber in order to have a symmetric equals

   *  method, but that implies implementing java.lang.Number as well.

   *

   *  Note - these are inlined because they are value classes, but

   *  the call to xxxWrapper is not eliminated even though it does nothing.

   *  Even inlined, every call site does a no-op retrieval of Predef's MODULE$

   *  because maybe loading Predef has side effects!

   */

  @inline implicit def byteWrapper(x: Byte)       = new runtime.RichByte(x)

  @inline implicit def shortWrapper(x: Short)     = new runtime.RichShort(x)

  @inline implicit def intWrapper(x: Int)         = new runtime.RichInt(x)

  @inline implicit def charWrapper(c: Char)       = new runtime.RichChar(c)

  @inline implicit def longWrapper(x: Long)       = new runtime.RichLong(x)

  @inline implicit def floatWrapper(x: Float)     = new runtime.RichFloat(x)

  @inline implicit def doubleWrapper(x: Double)   = new runtime.RichDouble(x)

  @inline implicit def booleanWrapper(x: Boolean) = new runtime.RichBoolean(x)

[Miguel Garcia]

Well, not all is lost. Until a purity analysis arrives, the new optimizer can check (intra-method) whether a given module has been loaded (for all code-paths leading to the program point in question) and if so consider the side-effects (if any) of the module's constructor to have been honored. I'll add it to the TODO list. BTW, here's the latest incarnation of the new optimizer:

  https://github.com/magarciaEPFL/scala/compare/master...GenRefactored14


Miguel
http://lampwww.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/

[Paul Phillips]

On Thu, Mar 28, 2013 at 1:54 PM, Miguel Garcia <miguel...@tuhh.de> wrote:

Well, not all is lost. Until a purity analysis arrives, the new optimizer can check (intra-method) whether a given module has been loaded (for all code-paths leading to the program point in question) and if so consider the side-effects (if any) of the module's constructor to have been honored. I'll add it to the TODO list. BTW, here's the latest incarnation of the new optimizer:

Even just getting Predef to be considered "loaded" (a real stretch scalac, I know) would make a huge difference.

[martin odersky]

On Fri, Mar 1, 2013 at 1:24 AM, Miguel Garcia <miguel...@tuhh.de> wrote:

To give an example:

  /** closures that are instantiated at least once, after dead code elimination */
  val liveClosures: mutable.Set[Symbol] = new mutable.HashSet()

The class-symbols added to that set are reachable via other means, the Set[Symbol] is used just to demarcate a subset of interest:

  for ((sym, cls) <- icodes.classes if inliner.isClosureClass(sym) && !deadCode.liveClosures(sym)) {
    . . .
  }

Sure but why would a Set[Int] be more compact than a Set[Symbol]? 

 - Martin

 

Miguel
http://lampwww.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/

On Friday, March 1, 2013 12:57:31 AM UTC+1, Miguel Garcia wrote:

Just to clarify, in those cases where it's clear the Symbol are reachable and will stay so, e.g. via Trees.

Provided that's the case, Set[Symbol] as well as Maps with Symbol-keys; could use Int identities instead.


Miguel
http://lampwww.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/


On Friday, March 1, 2013 12:36:35 AM UTC+1, Miguel Garcia wrote:

In the compiler, frequently a Set[Symbol] is used just for testing membership and adding symbols. In those cases, a Set[Int] containing symbol ids would equally do.

It's a low-hanging fruit that makes for lower GC.

Any disadvantages?


Miguel
http://lampwww.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--
Martin Odersky
Prof., EPFL and Chairman, Typesafe
PSED, 1015 Lausanne, Switzerland
Tel. EPFL: +41 21 693 6863
Tel. Typesafe: +41 21 691 4967

[Paul Phillips]

On Thu, Mar 28, 2013 at 3:29 PM, martin odersky <martin....@epfl.ch> wrote:

Sure but why would a Set[Int] be more compact than a Set[Symbol]? 

It wouldn't; hypothetical "IntSet" would be.

[Miguel Garcia]

A Set[Symbol] holding N elements implies N pointers for the garbage collector to track, adding one incoming-pointer to each of those N symbols. No such overhead with a Set[Int] which, granted, takes the same space in memory. Moreover, the same API as for Set[Symbol] can be used:
  https://github.com/magarciaEPFL/scala/commit/30d638b48d71e26bf444aee458c2250bfd4dfae1


Miguel
http://lampwww.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/

[Paul Phillips]

By the way, since symbol ids climb monotonically from 1, the high 12 or so bits will always be 0. That's almost a factor of two compression compared to 32 bits - and references can't even get down to 32.

[Rex Kerr]

How much time/space is spent on this compared to other things, by the way?  I'd have thought it's minimal.

If it's not minimal, there are various tricks you can play to improve the speed of hash lookup.  For example, if you have a few free bits and you don't often subtract things, you can encode a "check the next bin" flag with the top bit, which allows you to have a higher load factor before your lookups get too long; things fit in cache better too, etc..  Also, since the IDs are sequential anyway, the benefits of randomizing the IDs rather than just masking the bottom bits is probably minimal.  And you can decide that everything will be powers of two, so you will mask instead of using modulus.

I'd be surprised if all these tricks were necessary, but this is an area where factors of two improvement are quite possible.

(Also, right now, Miguel's implementation maxes out at 2M keys before overflowing, thanks to the *1000 / 450 trick.  I daresay that converting to a Long to avoid that issue would not impede performance too much.)

  --Rex

On Thu, Mar 28, 2013 at 6:48 PM, Paul Phillips <pa...@improving.org> wrote:

By the way, since symbol ids climb monotonically from 1, the high 12 or so bits will always be 0. That's almost a factor of two compression compared to 32 bits - and references can't even get down to 32.

--

[Paul Phillips]

On Thu, Mar 28, 2013 at 4:30 PM, Rex Kerr <ich...@gmail.com> wrote:

How much time/space is spent on this compared to other things, by the way?  I'd have thought it's minimal.

I don't know about space, but we do a ton of membership tests. What's the fastest way to test whether a given symbol is one of an immutable, smallish (say < 10) set of symbols? Like Set(UnitClass, BooleanClass, ByteClass, ShortClass, CharClass, IntClass, LongClass, FloatClass, DoubleClass).

[Erik Osheim]

On Thu, Mar 28, 2013 at 07:30:17PM -0400, Rex Kerr wrote:
> I'd be surprised if all these tricks were necessary, but this is an area
> where factors of two improvement are quite possible.

If you're willing to require the underlying array's size be a power of
two (which it looks like it will be here), you can also get an
improvement by storing a bitmask and using & rather than % to find
positions. Also, pre-computing and storing the size at which you'll
need to resize can make checkResize() a bit faster.

Also, I'd be tempted to do something a bit smarter than _ + 1 on hash
collisions, since that can get ugly pretty quickly in some cases.

Sorry to be a backseat author here. If I get a minute I'll try
benchmarking Miguel's example with some alternatives and see what seems
to work best.

-- Erik

[Ismael Juma]

On 28 Mar 2013 22:48, "Paul Phillips" <pa...@improving.org> wrote:
> and references can't even get down to 32.

What do you mean? References are 32 bits by default with HotSpot for heaps smaller than 32 GB.

That aside, implementing a specialised int set for Symbols that is more efficient for the desired use cases is worth exploring.

Ismael

[Paul Phillips]

On Thu, Mar 28, 2013 at 5:55 PM, Ismael Juma <ism...@juma.me.uk> wrote: 

What do you mean? References are 32 bits by default with HotSpot for heaps smaller than 32 GB.

There's zero overhead?

[Rex Kerr]

Can you give the symbols consecutive IDs?  If it's always those, you just make them 1-9.  Bounds testing is really fast, and no set needed.

If it's a random set of symbols, then it's harder.  If you have metrics on the relative number of constructions, and successful/unsuccessful tests, you can craft something with optimal performance.  Everything's a tradeoff, though, so it's hard to provide precise advice.  If you give me some numbers on what to expect, I can create something quasi-optimal.  Might be easier for me to actually do it than try to explain how.

  --Rex

[Rex Kerr]

On Mar 28, 2013 8:28 PM, "Erik Osheim" <er...@plastic-idolatry.com> wrote:
>
> On Thu, Mar 28, 2013 at 07:30:17PM -0400, Rex Kerr wrote:
> > I'd be surprised if all these tricks were necessary, but this is an area
> > where factors of two improvement are quite possible.
>
> If you're willing to require the underlying array's size be a power of
> two (which it looks like it will be here), you can also get an
> improvement by storing a bitmask and using & rather than % to find
> positions.

That's pretty much what I said ("mask instead of using modulus").

>Also, pre-computing and storing the size at which you'll
> need to resize can make checkResize() a bit faster.

Oh goodness, not on a modern processor.  You're much faster with a bit shift and an integer multiplication.  Even floating point multiply could be faster.

>
> Also, I'd be tempted to do something a bit smarter than _ + 1 on hash
> collisions, since that can get ugly pretty quickly in some cases.

But it is lovely for avoiding cache misses, and it's a very fast operation, and it makes subtraction easy.  Unless you expect periodic structure at some non-negligible power 2, I wouldn't worry about it.  See my point about encoding continuations in the high bit, though.

>
> Sorry to be a backseat author here. If I get a minute I'll try
> benchmarking Miguel's example with some alternatives and see what seems
> to work best.

'k, I'll leave this one to you unless you suggest otherwise.

  --Rex

[Ismael Juma]

Zero memory overhead for Java references (native references are still 64-bit and actual Java objects have more overhead in 64-bit JVMs). There is no CPU overhead for less than 4GB and low overhead for heaps between 4-32GB. Better cache utilisation is worth the CPU overhead in a lot of cases.

Best,
Ismael

[Erik Osheim]

On Thu, Mar 28, 2013 at 08:28:42PM -0400, Erik Osheim wrote:
> Sorry to be a backseat author here. If I get a minute I'll try
> benchmarking Miguel's example with some alternatives and see what seems
> to work best.

So, here's what I could come up with in an evening. I benchmarked
Miguel's code against two versions I wrote (Erik1 and Erik2). These
were based on the mutable set implementation in Debox but obviously
specialized for the use-case of only storing positive integers.

The big difference between Erik1 and Erik2 is the hashing strategy.
Erik1 uses a strategy similar to Miguel's (byteswap32 for initial hash
and then +1 for collisions) whereas Erik2 uses the strategy from Debox
(simple initial hash with shifting/permuting after collisions to
re-hash). Both versions use masking instead of modulus/division, and
both use a stored limit for now.

I tested for sets between 16-16k elements using random positive
integers. It didn't seem like larger sets were going to be the common
case and I am impatient. None of the classes currently do any checking
to make sure inputs are valid (>0).

The results are interesting. Both Erik1 and Erik2 are faster than
Miguel's example in most cases, although Erik1 degrades in the case of
larger sets, doing worse on the contains() test when n>=1024. Erik2 is
better than Miguel in all cases, and better than Erik1 in all cases
when n>=64. So this seems to prove my hunch that the +1 collision
strategy doesn't hold up well overall (at least on random data).

I've included a chart. The final column (m/e2) measures the ratio of
Miguel's example to Erik2 (so a value of 2 means that Erik2 ran twice
as fast on that test). Erik2 is a lot faster for insertion and deletion
tests (2-6x faster) and around 2x as fast for most apply() tests.

1. building the set (+=) times in ns
miguel erik1 erik2 m/e2
16 327 92 142 2.30
32 864 229 326 2.65
64 1699 411 326 5.21
256 7141 1997 1464 4.88
1024 35693 11940 5709 6.25
4096 194044 72451 32953 5.89
16384 829747 667801 216838 3.83

2. testing the set (apply) times in ns
miguel erik1 erik2 m/e2
16 82 41 32 2.56
32 153 69 64 2.39
64 321 208 173 1.86
256 1335 1074 721 1.85
1024 5528 9725 2748 2.01
4096 24693 60693 15539 1.59
16384 122647 377747 110983 1.11

3. emptying the set (-=) times in ns
miguel erik1 erik2 m/e2
16 204 61 64 3.19
32 427 98 121 3.53
64 923 246 222 4.16
256 3767 1193 993 3.79
1024 14928 10184 3792 3.94
4096 70753 55549 24625 2.87
16384 340240 356639 138138 2.46

I measured the results in Caliper. I've attached the Scala source file
I used (which includes the Caliper benchmarks and the IntSet
implementations) as well as the Build.scala file I used to run the
tests in SBT. I have not (yet) written any ScalaCheck tests to be sure
the implementations work, although when I tested them by hand they
seemed to, and the Debox code they are based on is tested.

I'd be happy to clean up the Erik2 implementation and submit it to
Scala if that seems useful to someone. Also, if Rex or anyone else
cares to try to improve further or try an alternate approach I'd be
interested to see the results.

-- Erik

[Miguel Garcia]

Erik,

It would be great if you could contribute the winning IntSet implementation, for use in scalac (that's my short term use case, others might want to use it off the library, but that's another story).

I'm also starting to merge the other ideas from this thread, over the next few days. Thanks!


Miguel
http://lampwww.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/

[Rex Kerr]

On Thu, Mar 28, 2013 at 11:48 PM, Erik Osheim <er...@plastic-idolatry.com> wrote:

On Thu, Mar 28, 2013 at 08:28:42PM -0400, Erik Osheim wrote:
> Sorry to be a backseat author here. If I get a minute I'll try
> benchmarking Miguel's example with some alternatives and see what seems
> to work best.

I'd be happy to clean up the Erik2 implementation and submit it to
Scala if that seems useful to someone. Also, if Rex or anyone else
cares to try to improve further or try an alternate approach I'd be
interested to see the results.

I don't really have any ideas left that you haven't already implemented; Erik2 looks like a good overall winner.  I guess I'll try a batched IntSet, but these usually lose to flat schemes.  You'll need to fix subtraction, however.  Observe:

scala> val e = IntSetErik2.empty
e: IntSetErik2 = <function1>

scala> e += 8
res34: Boolean = true

scala> e += 16
res35: Boolean = true

scala> e(8)
res36: Boolean = true

scala> e(16)
res37: Boolean = true

scala> e -= 16
res38: Boolean = true

scala> e(8)
res39: Boolean = false

Hopefully sane subtraction is compatible with your nonsequential jump scheme.  (I couldn't quite figure out what your subtraction was supposed to do, actually.)

  --Rex

[Erik Osheim]

On Fri, Mar 29, 2013 at 12:16:15PM -0400, Rex Kerr wrote:
> I don't really have any ideas left that you haven't already implemented;
> Erik2 looks like a good overall winner. I guess I'll try a batched IntSet,
> but these usually lose to flat schemes. You'll need to fix subtraction,
> however. Observe:

Ooh, good catch! It was a minor comparison bug. I'm writing tests now
and re-running the benchmarks. I don't *think* it is a problem in the
design, but of course until testing and benchmarking are done I can't
be 100% certain.

> Hopefully sane subtraction is compatible with your nonsequential jump
> scheme. (I couldn't quite figure out what your subtraction was supposed to
> do, actually.)

The basic idea is that instead of trying to shift things back into the
newly opened slot, we just mark the slot as "used but without a value".
This means that during lookup we treat is as filled, but during
insertion we treat it as empty. This strategy works well if you don't
let your table get overly full, and if you have a good collision
strategy. Once you rehash, the "marked but empty" slots will disappear.

-- Erik

[Rex Kerr]

Yeah, I got that--I had planned to do the same.  I just wasn't 100% sure of your marking scheme, though, so I couldn't (quickly) figure out how to fix the bug.

 --Rex

[Rex Kerr]

On Fri, Mar 29, 2013 at 12:16 PM, Rex Kerr <ich...@gmail.com> wrote:

On Thu, Mar 28, 2013 at 11:48 PM, Erik Osheim <er...@plastic-idolatry.com> wrote:

On Thu, Mar 28, 2013 at 08:28:42PM -0400, Erik Osheim wrote:
> Sorry to be a backseat author here. If I get a minute I'll try
> benchmarking Miguel's example with some alternatives and see what seems
> to work best.

I'd be happy to clean up the Erik2 implementation and submit it to
Scala if that seems useful to someone. Also, if Rex or anyone else
cares to try to improve further or try an alternate approach I'd be
interested to see the results.

I don't really have any ideas left that you haven't already implemented; Erik2 looks like a good overall winner.  I guess I'll try a batched IntSet, but these usually lose to flat schemes. 

FWIW, batched IntSet does indeed lose to the flat scheme (by almost 2x).

And also I don't notice much difference between the simple +1 scheme and your more complicated mixing (taking otherwise identical code) in my benchmarks.  As long as there're no bugs, there's no harm in adopting the more complex one.

  --Rex