Typedefining an Int

You look in need of a java.util.BitSet. I don't know of there is an equivalent in Scala but the java does what you need.

-M.


From: Robert James <srobertjames@gmail.com>
To: Scala List <scala@listes.epfl.ch>
Sent: Tuesday, July 28, 2009 9:29:27 AM
Subject: [scala] Typedefining an Int

I have an integer value which I use to store flags in it.  It's just an integer - I have _a lot_ of them, and so for performance reasons, I don't want it to be a heap allocated, garbage collected, pointer -> class header+int  object.
However, I'd like to make the code more readable by using the type name MyField as opposed to Int.  I'd be even happier if I could define (pure) functions on it as methods, so I could type   f.isFlagSet(3)instead of  isFlagSet(f, 3)Is there anyway to do any of the above without using a full blown heap allocated object (which would at least quadruple the memory usage)?
Be smarter than spam. See how smart SpamGuard is at giving junk email the boot with the All-new Yahoo! Mail

Don't optimize prematurely!
Use an Int, the compiler is pretty good at converting to use primitives if necessary.I'd also not go out of my way to avoid the heap unless a good profiler told me that it would have a major benefit in a performance-critical section of code.

On Tue, Jul 28, 2009 at 2:29 PM, Robert James <srobertjames@gmail.com> wrote:

I have an integer value which I use to store flags in it.  It's just an integer - I have _a lot_ of them, and so for performance reasons, I don't want it to be a heap allocated, garbage collected, pointer -> class header+int  object.
However, I'd like to make the code more readable by using the type name MyField as opposed to Int.  I'd be even happier if I could define (pure) functions on it as methods, so I could type   f.isFlagSet(3)instead of  isFlagSet(f, 3)Is there anyway to do any of the above without using a full blown heap allocated object (which would at least quadruple the memory usage)?

On Tuesday July 28 2009, Martin Renaud wrote:
> You look in need of a java.util.BitSet. I don't know of there is an
> equivalent in Scala but the java does what you need.

> -M.

Randall Schulz

> Use an Int, the compiler is pretty good at converting to use primitives if
> necessary.

This does not help him achieve his goal of having more readable code
than Int affords. He also did not express any performance problem
with the use of Int.

2009/7/28 Kevin Wright :
> Don't optimize prematurely!
> Use an Int, the compiler is pretty good at converting to use primitives if
> necessary.
> I'd also not go out of my way to avoid the heap unless
> a good profiler told me that it would have a major benefit in a performance-critical section of code.
>
> On Tue, Jul 28, 2009 at 2:29 PM, Robert James
> wrote:
>>
>> I have an integer value which I use to store flags in it.  It's just an
>> integer - I have _a lot_ of them, and so for performance reasons, I don't
>> want it to be a heap allocated, garbage collected, pointer -> class
>> header+int  object.
>> However, I'd like to make the code more readable by using the type name
>> MyField as opposed to Int.  I'd be even happier if I could define (pure)
>> functions on it as methods, so I could type
>>   f.isFlagSet(3)
>> instead of
>>   isFlagSet(f, 3)
>> Is there anyway to do any of the above without using a full blown heap
>> allocated object (which would at least quadruple the memory usage)?
>

Neat! I first got excited about BitSet.  But, looking at it further, it seems to be a heap allocated object.  Its main benefit is methods to access individual bits - which I've already written equivalents acting on Ints.
I'll explain a bit: My application is a large algorithm, crunching millions of these flags, looking for certain patterns.  If I store them as Ints, it's 4 bytes per flagset.  If I store them as heap objects, it's 4 bytes for a pointer, plus 8 bytes (or is it 12?) for the object header, plus 4 bytes for the flagset itself.  Which means I'll quadruple my memory usage.  When you have millions of these to crunch, that's a heavy burden. > Don't optimize prematurely!Agreed.  The key word being _prematurely_.  This should not be construed as "Don't optimize, ever!".  As I said, I've already done enough prototyping to be happy with this, and to know that I don't want the memory to go up four fold.  My goal now is simply to improve the readability, by being able to use an alias for Int, and perhaps by being able to pretend my functions are methods of Int. On Tue, Jul 28, 2009 at 9:51 AM, Randall R Schulz <rschulz@sonic.net> wrote:

On Tuesday July 28 2009, Martin Renaud wrote:
> You look in need of a java.util.BitSet. I don't know of there is an
> equivalent in Scala but the java does what you need.

<http://www.scala-lang.org/docu/files/api/scala/collection/BitSet.html>
<http://www.scala-lang.org/docu/files/api/scala/collection/immutable/BitSet.html>
<http://www.scala-lang.org/docu/files/api/scala/collection/mutable/BitSet.html>


> -M.


Randall Schulz

There is one big case when avoiding the heap is critical: mobile apps.

2009/7/28 Kevin Wright <kev.lee.wright@googlemail.com>

Don't optimize prematurely!
Use an Int, the compiler is pretty good at converting to use primitives if necessary. I'd also not go out of my way to avoid the heap unless a good profiler told me that it would have a major benefit in a performance-critical section of code.

On Tue, Jul 28, 2009 at 2:29 PM, Robert James <srobertjames@gmail.com> wrote:

I have an integer value which I use to store flags in it.  It's just an integer - I have _a lot_ of them, and so for performance reasons, I don't want it to be a heap allocated, garbage collected, pointer -> class header+int  object.
However, I'd like to make the code more readable by using the type name MyField as opposed to Int.  I'd be even happier if I could define (pure) functions on it as methods, so I could type   f.isFlagSet(3)instead of  isFlagSet(f, 3)Is there anyway to do any of the above without using a full blown heap allocated object (which would at least quadruple the memory usage)?

--
Thanks,
-Vlad

Makes sense if you have multiple ints, all individually heap allocated, but why not bundle them together in a single array or a few large arrays to eliminate some of the overhead?  Then maybe consider something like the flyweight pattern for operating over the array(s)


On Tue, Jul 28, 2009 at 4:33 PM, Robert James <srobertjames@gmail.com> wrote:

Neat! I first got excited about BitSet.  But, looking at it further, it seems to be a heap allocated object.  Its main benefit is methods to access individual bits - which I've already written equivalents acting on Ints.
I'll explain a bit: My application is a large algorithm, crunching millions of these flags, looking for certain patterns.  If I store them as Ints, it's 4 bytes per flagset.  If I store them as heap objects, it's 4 bytes for a pointer, plus 8 bytes (or is it 12?) for the object header, plus 4 bytes for the flagset itself.  Which means I'll quadruple my memory usage.  When you have millions of these to crunch, that's a heavy burden. > Don't optimize prematurely!Agreed.  The key word being _prematurely_.  This should not be construed as "Don't optimize, ever!".  As I said, I've already done enough prototyping to be happy with this, and to know that I don't want the memory to go up four fold.  My goal now is simply to improve the readability, by being able to use an alias for Int, and perhaps by being able to pretend my functions are methods of Int. On Tue, Jul 28, 2009 at 9:51 AM, Randall R Schulz <rschulz@sonic.net> wrote:

On Tuesday July 28 2009, Martin Renaud wrote:
> You look in need of a java.util.BitSet. I don't know of there is an
> equivalent in Scala but the java does what you need.

<http://www.scala-lang.org/docu/files/api/scala/collection/BitSet.html>
<http://www.scala-lang.org/docu/files/api/scala/collection/immutable/BitSet.html>
<http://www.scala-lang.org/docu/files/api/scala/collection/mutable/BitSet.html>


> -M.


Randall Schulz

On Tue, Jul 28, 2009 at 11:40 AM, Kevin Wright <kev.lee.wright@googlemail.com> wrote:

Makes sense if you have multiple ints, all individually heap allocated, but why not bundle them together in a single array or a few large arrays to eliminate some of the overhead?  Then maybe consider something like the flyweight pattern for operating over the array(s)

There arranged on a tree, dynamically - the structure is changed as the algorithm evolves.  Regardless, I'd like to know if there's any way to typedef an Int, or treat a local value as an object without actually heap allocating it. 

Not until some of the stuff in the Da Vinci project makes it into the JVM... :(

On Tue, Jul 28, 2009 at 4:49 PM, Robert James <srobertjames@gmail.com> wrote:

On Tue, Jul 28, 2009 at 11:40 AM, Kevin Wright <kev.lee.wright@googlemail.com> wrote:

Makes sense if you have multiple ints, all individually heap allocated, but why not bundle them together in a single array or a few large arrays to eliminate some of the overhead?  Then maybe consider something like the flyweight pattern for operating over the array(s)

There arranged on a tree, dynamically - the structure is changed as the algorithm evolves.  Regardless, I'd like to know if there's any way to typedef an Int, or treat a local value as an object without actually heap allocating it. 

It seems that it's possible to do my first goal:
     type Flagset = Intbut not my second (define methods on Flagset)
On Tue, Jul 28, 2009 at 4:49 PM, Robert James <srobertjames@gmail.com> wrote:

I'd like to know if there's any way to typedef an Int, or treat a local value as an object without actually heap allocating it. 

I'm sure there is a flaw in this somewhere, but perhaps escape analysis in
Java 6 update 14 will help?
http://java.sun.com/javase/6/webnotes/6u14.html
-XX:+DoEscapeAnalysis

Since you have your objects stored in a hierarchy, this certainly won't
work unless you keep them that way. But I wonder if you could create an
implicit conversion to take the Int (or Flagset, though I have never tried
implicits with type definitions) to a object (like BitSet) that implements
the isFlagSet/other methods and get your result?

The trouble is that I'm not sure if this more complicated use-case
qualifies for the current method escaping, so maybe it won't work...
Perhaps still worth a try?

Kieron

Robert James wrote on 28/07/2009 17:07:06:
> It seems that it's possible to do my first goal:
> type Flagset = Int
> but not my second (define methods on Flagset)
>
> On Tue, Jul 28, 2009 at 4:49 PM, Robert James
wrote:
>

> I'd like to know if there's any way to typedef an Int, or treat a
> local value as an object without actually heap allocating it.

This message may contain confidential and privileged information and is intended solely for the use of the named addressee. Access, copying or re-use of the e-mail or any information contained therein by any other person is not authorised. If you are not the intended recipient please notify us immediately by returning the e-mail to the originator and then immediately delete this message. Although we attempt to sweep e-mail and attachments for viruses, we do not guarantee that either are virus-free and accept no liability for any damage sustained as a result of viruses.

Please refer to http://www.bnymellon.com/disclaimer/piml.html for certain disclosures.

On Tue, Jul 28, 2009 at 5:20 PM, wrote:
> But I wonder if you could create an
> implicit conversion to take the Int (or Flagset, though I have never tried
> implicits with type definitions) to a object (like BitSet) that implements
> the isFlagSet/other methods and get your result?

The following it totally gross and unsafe and should _never_ be used
for _anything_,

scala> object IntWrapper { var i = 0 ; def foo = i^0xcccccccc }
defined module IntWrapper

scala> implicit def wrapInt(i : Int) = { IntWrapper.i = i ; IntWrapper }
wrapInt: (Int)object IntWrapper

scala> 23.foo
res0: Int = -858993445

Cheers,

Miles

clever!  too bad it's not thread-safe.  what if IntWrapper is inside a ThreadLocal instead...

On Wed, Jul 29, 2009 at 12:49 AM, Miles Sabin <miles@milessabin.com> wrote:

On Tue, Jul 28, 2009 at 5:20 PM, <Kieron.Wilkinson@paretopartners.com> wrote:
> But I wonder if you could create an
> implicit conversion to take the Int (or Flagset, though I have never tried
> implicits with type definitions) to a object (like BitSet) that implements
> the isFlagSet/other methods and get your result?

The following it totally gross and unsafe and should _never_ be used
for _anything_,

scala> object IntWrapper { var i = 0 ; def foo = i^0xcccccccc }
defined module IntWrapper

scala> implicit def wrapInt(i : Int) = { IntWrapper.i = i ; IntWrapper }
wrapInt: (Int)object IntWrapper

scala> 23.foo
res0: Int = -858993445

Cheers,


Miles

--
Miles Sabin
tel: +44 (0)7813 944 528
skype:  milessabin
http://www.chuusai.com/
http://twitter.com/milessabin

--
.......__o
.......\<,
....( )/ ( )...

> MyField as opposed to Int.  I'd be even happier if I could define (pure)
> functions on it as methods, so I could type
>   f.isFlagSet(3)
> instead of
>   isFlagSet(f, 3)

Maybe you'll be better of turning it around. Instead of asking the
field about flags, ask the flags about fields.

Flag3 isSetFor f

or

f match {
case Flag3 => doSomething
}

You could even make some DSL for your algorithm by defining apropriate
Flag combinators

BR,
John

On Tue, Jul 28, 2009 at 6:18 PM, Walter Chang wrote:
> clever!

No really not clever at all ... ;-)

> too bad it's not thread-safe. what if IntWrapper is inside a
> ThreadLocal instead...

I really doubt that using a ThreadLocal would be a win here relative
to the much saner and safer,

implicit def wrapInt(i : Int) = new IntWrapper(i)
class IntWrapper(i : Int) {
def foo = i^0xcccccccc
}

Where Hotspot with -XX:+DoEscapeAnalysis should do reasonably well.

Cheers,

Miles

You could do pimp my library:

class OneWordBitset(i: Int) {
def contains(f: Int) = ...
// other methods you want
}

object OneWordBitset {
implicit def bitsetFromInt(i: Int) = new OneWordBitset(i)
}

Then you can call 12.hasFlag(3). This will create a OneWordBitset each time
you call .contains on an Integer, but as soon as .contains returns the
created OneWordBitset is garbage and can be garbage collected, so your space
usage is the same. On the other hand, it is kind of unfortunate that you
need to allocate a temporary object just to be able to write
object.method(arg) instead of method(object, arg).

David MacIver has an amusing post relevant to this:

"OO has contributed many big and important innovations to programming. Among
these, the foremost is that you write functions after rather than before
their argument."

http://www.drmaciver.com/2009/01/writing-things-right/

Paul

problem with pimping is that the wrapper objects then end up on the heap.  Depending on the exact algorithms and pattern of access, this means that you're back to the same memory usage as just storing bitsets on the heap.

On Tue, Jul 28, 2009 at 7:44 PM, Paul Chiusano <paul.chiusano@gmail.com> wrote:

You could do pimp my library:

class OneWordBitset(i: Int) {
 def contains(f: Int) = ...
 // other methods you want
}

object OneWordBitset {
 implicit def bitsetFromInt(i: Int) = new OneWordBitset(i)
}

Then you can call 12.hasFlag(3). This will create a OneWordBitset each time
you call .contains on an Integer, but as soon as .contains returns the
created OneWordBitset is garbage and can be garbage collected, so your space
usage is the same. On the other hand, it is kind of unfortunate that you
need to allocate a temporary object just to be able to write
object.method(arg) instead of method(object, arg).

David MacIver has an amusing post relevant to this:

"OO has contributed many big and important innovations to programming. Among
these, the foremost is that you write functions after rather than before
their argument."

http://www.drmaciver.com/2009/01/writing-things-right/

Paul
--
View this message in context: http://www.nabble.com/-scala--Typedefining-an-Int-tp24699591p24705643.html
Sent from the Scala mailing list archive at Nabble.com.

Depending on the exact algorithms and pattern of access, this means that you're back to the same memory usage as just storing bitsets on the heap.

This is not correct. In the code I gave, the object is allocated on the heap only at the point when the method is called, and as soon as the method returns it is garbage - these temporaries are never stored. So the memory usage will be the same as before. There will just be an additional runtime cost for each call, and possibly more frequent garbage collection.
View this message in context: Re: [scala] Typedefining an Int
Sent from the Scala mailing list archive at Nabble.com.

One ideal solution would be dynamic composition, allowing a trait to extend an instantiated object instance instead of a class or trait.We'd then get language level support for the flyweight, proxy and decorator design patterns.



On Tue, Jul 28, 2009 at 8:39 PM, Paul Chiusano <paul.chiusano@gmail.com> wrote:

Depending on the exact algorithms and pattern of access, this means that you're back to the same memory usage as just storing bitsets on the heap.

This is not correct. In the code I gave, the object is allocated on the heap only at the point when the method is called, and as soon as the method returns it is garbage - these temporaries are never stored. So the memory usage will be the same as before. There will just be an additional runtime cost for each call, and possibly more frequent garbage collection.
View this message in context: Re: [scala] Typedefining an Int
Sent from the Scala mailing list archive at Nabble.com.