[vwnc] HELP . some ideas on decompiled code wrong??

Hi Alan,

Yes, it’s used a lot when adding items to a collection, but I think it’s hardly used when using do:, select:, reject:, collect:, detect:, contains:,... You normally don’t add or remove items from a collection while using one of the previous methods.

If you’d want to modify a collection while looping over it, you probably don’t use do: anyway, so I think it would be no problem at all to disallow the use of #become: on a collection while you’re performing one of the messages above. You could make a bytecode (just like you could do for #to:do:) called #from:to:do: that loops over all indexed vars of an object between from: and to: and that disallows a become: with the receiver while it’s looping.

Summarized you can have a performance gain on:

-        #to:do: à no integer type checking and overflow checking during the loop

-        #to:by:do: à same as above

-        Collection>>from:to:do: à no integer type checking, overflow checking, range checking, method lookup for #at: during the loop

Is there a way to predict what the performance gain would be if you would have these changes?

For instance:

Time millisecondsToRun: [1 to: 100000000 do: [:i |]]

takes 550 millisecs on my PC. What would the result be if you’d do it without the checking?

Mark

become: happens a lot in collection operations in VW - usually, but not exclusively, to increase size

At 12:28 PM 10/30/2008, Mark Plas wrote:

"How does one prematurely range check that?"

Good example: changing the collection while looping over it. But your example is a bit misleading. It wouldn't be the #at: in your example that gets optimized, it would be the #basicAt: used in the #apply:from:to: method that Paul mentions.

But let's look a bit closer at your example. If you would slightly change it to this:

        |collection|
        collection := Object comment asString
                runsFailing: [:c | c isSeparator].
        1 to: collection size do: [:n |
                collection removeFirst.
                collection basicAt: n].

then it doesn't crash anymore. I used a #basicAt: instead of #at:

it's interesting to know that OrderedCollection>>do: wouldn't crash either if you did:

        | collection idx |
        collection := #(1 2 3 4 5) asOrderedCollection.
        idx := 0.
        collection do: [:each | collection removeLast.
                idx := idx + 1].
        idx

it will print '5'. This could be seen as a bug in the implementation.

It would however crash in this case:

        | collection |
        collection := #(1 2 3 4 5) asOrderedCollection.
        collection do: [:each | collection become: (OrderedCollection basicNew: 0)]

...because I used #become: to reduce the number of indexed vars. So range checking is necessary.

This is what OrderedCollection>>do: looks like:

OrderedCollection>>do: aBlock
        firstIndex to: lastIndex do:
                [:index | aBlock value: (self basicAt: index)]

It's the #basicAt: in this method that can be optimized I believe. If you know that firstIndex and lastIndex are in range before you start looping, then I think there's only one way that the #basicAt: could fail, and that would be because the collection got replaced via a #become: as shown above. (I don't know if there is another way to reduce the number of indexed vars other than using #become?).

It's unfortunate that this become would be the only reason while range checking is needed during the loop, because it happens rather exceptional (does it happen in 'normal' code?).

So here's a possible solution:

Suppose that, when using the 'optimizedDo:' method, a collection wouldn't be allowed to #become: something else. If it isn't allowed to swap to another object, then you can completely optimize the inner workings of #optimizedDo:.

#optimizedDo: would be implemented like this:

OrderedCollection>>optimizedDo: aBlock
        self dontAllowBecome.
        ...do the optimized loop...
        self allowBecome.

If you would send #become: during the loop you'd get an exception: 'become not allowed while iterating over the object'.

Could this work?

Mark

-----Original Message-----
From: [hidden email] [[hidden email]] On Behalf Of Travis Griggs
Sent: donderdag 30 oktober 2008 15:37
To: [hidden email] NC
Subject: Re: [vwnc] HELP . some ideas on decompiled code wrong??


On Oct 30, 2008, at 1:15 AM, Mark Plas wrote:

> There's even a bug(?) in the to:do: optimization. We've implemented
> + on Date such that it adds a number of days to the date. By
> accident I've sent to:do: with Dates as arguments and it works just
> fine even though to:do: is only implemented on Number.
>
> I've always wondered why to:do: isn't implemented by using a special
> bytecode as Paul suggests. If the arguments of to:do: are both
> SmallIntegers a lot of type checking and checking for possible
> conversion to LargeIntegers could be avoided which I guess has to be
> done the way it is done now for every iteration in the loop. The
> same goes for the collection iteration primitive/bytecode Paul
> mentions. If you have that, the #at: doesn't need to check its
> arguments for type correctness or being in range either. You could
> do all the checking just once and not for every iteration in the loop.
>
> These may be simple extensions to the VM that could make things
> measurably faster.
>  different? Some constructs get compiled down in a way that the
> decompiler reconstructs them differently, but they still produce the
> same effect.  If you recompile the method, do you get the same
> bytecodes as if you compiled the decompiled source?

collection := Object comment asString runsFailing: #isSeparator.
1 to: collection size do: [:n | collection removeFirst. collection at:
n].

How does one prematurely range check that?

--
Travis Griggs
[hidden email]
"The dissenter is every human being at those moments of his life when
he resigns momentarily from the herd and thinks for himself." -
Archibald MacLeish, poet and librarian




_______________________________________________
vwnc mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/vwnc

_______________________________________________
vwnc mailing list
[hidden email]
http://lists.cs.uiuc.edu/mailman/listinfo/vwnc