local constants in functions or static locals/Hilbert curve in clojure (no images:)

[ajuc]

Hello.

I've tried to translate nice Hilbert-curve-index calculating function
to clojure (http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-
Spatial-indexing-with-Quadtrees-and-Hilbert-Curves).

I've got sth like that:

(def hilbert-map {
:a {[0 0] [0 :d], [0 1] [1 :a], [1 0] [3 :b], [1 1] [2 :a]}
:b {[0 0] [2 :b], [0 1] [1 :b], [1 0] [3 :a], [1 1] [0 :c]}
:c {[0 0] [2 :c], [0 1] [3 :d], [1 0] [1 :c], [1 1] [0 :b]}
:d {[0 0] [0 :a], [0 1] [3 :c], [1 0] [1 :d], [1 1] [2 :d]} } )

(defn point-to-hilbert
"Return index of point (x,y) on Hilbert curve defined on square
(2^order)*(2^order).
x,y should be in 0 .. (2^order)-1
result will be in 0 .. (2^(order*2))-1"
[x y order]
(let [step-inside (fn [x i] (if (== 0 (bit-and x (bit-shift-left 1
i))) 0 1))
step (fn [square i] ((hilbert-map square) [(step-inside x i)
(step-inside y i)]))]
(loop [ square :a, position 0, i (dec order)]
(if (< i (int 0))
position
(let [ v (step square i)]
(recur (v 1), (-> position (bit-shift-left 2) (bit-or (v
0))), (dec i)))))))

(time (dotimes [ _ (int 1000)] (point-to-hilbert (rand-int (int
-1000)) (int 1) (int 16))))


I would like to somehow hide the global hilbert-map into my function,
but I can't see how to do that.

Is this possible? I know that I can just inert literal into my let,
but that degrades performance, when function is called many times.

I would like to have something like static local variable in C++, or
just regular constant local variable in my function.

Besides, if you see a way to improve my code, please, tell how.

Greetings.

[John Harrop]

Just put the literal directly into the function.

 

Is this possible? I know that I can just inert literal into my let,
but that degrades performance, when function is called many times.

Have you tested it, using (time ...), preferably on the server VM? I wouldn't be surprised if a calculation that produces a constant gets optimized away to just the constant. 

[ajuc]

> > I would like to somehow hide the global hilbert-map into my function,
> > but I can't see how to do that.
>
> Just put the literal directly into the function.
>
> > Is this possible? I know that I can just inert literal into my let,
> > but that degrades performance, when function is called many times.
>
> Have you tested it, using (time ...), preferably on the server VM? I
> wouldn't be surprised if a calculation that produces a constant gets
> optimized away to just the constant.

(time (dotimes [_ (int 10000)] (point-to-hilbert (rand-int (int

-1000)) (int 1) (int 16))))

(time (dotimes [_ (int 10000)] (point-to-hilbert-2 (rand-int (int

-1000)) (int 1) (int 16))))

"Elapsed time: 892.041865 msecs" - version with global
"Elapsed time: 1152.569949 msecs" - version with literal in let
statement inside the function

I only tested on client java 6, I have to install enterprise jdk, I
think, to be able to add parameter -server to the command line, now it
returns error.
Anyway, requiring users of for example game, to install non standard
java just to have the game run at good speed isn't the best way, so
I'll probably optimize for java -client anyway.

[Wilson MacGyver]

The server VM is part of the standard JDK.

To use it you can either do

java -server

or

set environment variable JAVA_OPS like this on linux/OSX

export JAVA_OPTS="-server"

> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient with your first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en



--
Omnem crede diem tibi diluxisse supremum.

[John Harrop]

On Sat, Nov 14, 2009 at 6:19 AM, ajuc <aju...@gmail.com> wrote:

> > I would like to somehow hide the global hilbert-map into my function,
> > but I can't see how to do that.
>
> Just put the literal directly into the function.
>
> > Is this possible? I know that I can just inert literal into my let,
> > but that degrades performance, when function is called many times.
>
> Have you tested it, using (time ...), preferably on the server VM? I
> wouldn't be surprised if a calculation that produces a constant gets
> optimized away to just the constant.

(time (dotimes [_ (int 10000)] (point-to-hilbert (rand-int (int

-1000)) (int 1) (int 16))))

(time (dotimes [_ (int 10000)] (point-to-hilbert-2 (rand-int (int

-1000)) (int 1) (int 16))))

"Elapsed time: 892.041865 msecs" - version with global
"Elapsed time: 1152.569949 msecs" - version with literal in let
statement inside the function

Eeeuw.

Was this with a Clojure literal in the let, or with a non-trivial calculation using constants?

If it's with a literal, it's an optimization Rich can make pretty easily: if a function being compiled contains a let bind whose value, or a loop bind whose initial value, is (after macro expansion) pure data (no function or special form invocations -- just vectors, sets, maps, etc. with leaves that are integers, strings, doubles, etc.), then change that value to a private static final field in the function class, and in the "let" case the places where the function requests that variable can compile to bytecode to access that field. The "loop" case just requires the loop initialization grab the field value as the initial value of the loop binding, then behave as usual for the loop body and recur.

Some function and special form calls can even be allowed, with a little finesse: clojure.core/list for one, quote, and nested let:

(let [x (let [y [1 2]] [y y])] ...)

can be reduced to bytecode equivalent to this pseudo-Java

private static final IPersistentVector X = [[1 2] [1 2]];

public Object invoke blah blah blah {

    // ... uses X

}

[ajuc]

> Eeeuw.
>
> Was this with a Clojure literal in the let, or with a non-trivial
> calculation using constants?

The only difference is literal map of maps in let form.
Full code here: http://clojure.pastebin.com/m17b8d69


I have to install java one more time, when I try to start java -
server, I get:
Error: no `server' JVM at `F:\Program Files\Java\jre6\bin\server
\jvm.dll

The difference in speed isn't that bad, and I can understand why
clojure depends on hot-spot for performance, especially in such a
young stage of development. But this optimisation would be nice :)

[John Harrop]

On Sat, Nov 14, 2009 at 3:03 PM, ajuc <aju...@gmail.com> wrote:

I have to install java one more time, when I try to start java -

server, I get:
Error: no `server' JVM at `F:\Program Files\Java\jre6\bin\server
\jvm.dll

You need to use the one in F:\Program Files\Java\jdk6 instead.

I'm surprised your IDE didn't select that one automatically. Mine (Enclojure) did.

[ajuc]

My IDE is waterfront, and it just starts java, and in my path the
first java was jre, I've changed that, problem solved, thanks.

What's intresting, when I run the code in java -server, the difference
between using global, and using literal map expression in let got
bigger.

Now its:
"Elapsed time: 555.810305 msecs" - with global
vs
"Elapsed time: 1091.399046 msecs" - with literal in let

[John Harrop]

On Sun, Nov 15, 2009 at 4:49 AM, ajuc <aju...@gmail.com> wrote:

On 15 Lis, 00:21, John Harrop <jharrop...@gmail.com> wrote:

> On Sat, Nov 14, 2009 at 3:03 PM, ajuc <aju...@gmail.com> wrote:
> > I have to install java one more time, when I try to start java -
> > server, I get:
> > Error: no `server' JVM at `F:\Program Files\Java\jre6\bin\server
> > \jvm.dll
>
> You need to use the one in F:\Program Files\Java\jdk6 instead.
>
> I'm surprised your IDE didn't select that one automatically. Mine
> (Enclojure) did.

My IDE is waterfront, and it just starts java, and in my path the
first java was jre, I've changed that, problem solved, thanks.

What's intresting, when I run the code in java -server, the difference
between using global, and using literal map expression in let got
bigger.

That's very odd.

Rich needs to take a look at this. Letting a constant shouldn't have a performance hit, IMO.

Could you test whether it's faster to use your complex data structure directly in the function, anonymously at the point of use, or to yank it from a global var?

[ajuc]

> That's very odd.
>
> Rich needs to take a look at this. Letting a constant shouldn't have a
> performance hit, IMO.
>
> Could you test whether it's faster to use your complex data structure
> directly in the function, anonymously at the point of use, or to yank it
> from a global var?

Code (can you run it on your computer to verify?):
http://clojure.pastebin.com/f508ad31b

My results (I've increased N to 100000 and cached random coordinates
in vector, to supply the same points to each version of function):

"Elapsed time: 2990.418336 msecs"
"point-to-hilbert-directly-from-global " nilnil

"Elapsed time: 2488.745357 msecs"
"point-to-hilbert-let-from-global " nilnil

"Elapsed time: 3669.685672 msecs"
"point-to-hilbert-literal-in-let " nilnil

"Elapsed time: 13039.499434 msecs"
"point-to-hilbert-literal-in-place " nilnil

With literal in place it is 10 seconds slower.

[Michael Wood]

2009/11/15 ajuc <aju...@gmail.com>:

>
>> That's very odd.
>>
>> Rich needs to take a look at this. Letting a constant shouldn't have a
>> performance hit, IMO.
>>
>> Could you test whether it's faster to use your complex data structure
>> directly in the function, anonymously at the point of use, or to yank it
>> from a global var?
>
> Code (can you run it on your computer to verify?):
> http://clojure.pastebin.com/f508ad31b

Here are my results on Linux with the server VM, after fixing the typo
(glocal -> global) and changing pr to println:

http://clojure.pastebin.com/f49f16d71

"Elapsed time: 2110.721659 msecs"
point-to-hilbert-directly-from-global nil

"Elapsed time: 1197.547328 msecs"
point-to-hilbert-let-from-global nil

"Elapsed time: 1884.777766 msecs"
point-to-hilbert-literal-in-let nil

"Elapsed time: 4847.630084 msecs"
point-to-hilbert-literal-in-place nil

$ java -version
java version "1.6.0_0"
OpenJDK Runtime Environment (IcedTea6 1.4.1) (6b14-1.4.1-0ubuntu12)
OpenJDK Client VM (build 14.0-b08, mixed mode, sharing)

Although, running it again now, I get:

"Elapsed time: 3278.709938 msecs"
point-to-hilbert-directly-from-global nil

"Elapsed time: 1234.739782 msecs"
point-to-hilbert-let-from-global nil

"Elapsed time: 1945.980422 msecs"
point-to-hilbert-literal-in-let nil

"Elapsed time: 5737.756701 msecs"
point-to-hilbert-literal-in-place nil

And after rearranging them, I get:

"Elapsed time: 2506.30872 msecs"
point-to-hilbert-let-from-global nil

"Elapsed time: 2091.866122 msecs"
point-to-hilbert-literal-in-let nil

"Elapsed time: 1309.805767 msecs"
point-to-hilbert-directly-from-global nil

"Elapsed time: 5228.071194 msecs"
point-to-hilbert-literal-in-place nil

So it seems you need to allow Hotspot to optimise it:

"Elapsed time: 3084.796868 msecs"
point-to-hilbert-literal-in-let nil

"Elapsed time: 1354.13218 msecs"
point-to-hilbert-literal-in-let nil

"Elapsed time: 1340.907318 msecs"
point-to-hilbert-literal-in-let nil

"Elapsed time: 1338.655641 msecs"
point-to-hilbert-literal-in-let nil

and:

"Elapsed time: 2393.682633 msecs"
point-to-hilbert-let-from-global nil

"Elapsed time: 990.713252 msecs"
point-to-hilbert-let-from-global nil

"Elapsed time: 1008.451391 msecs"
point-to-hilbert-let-from-global nil

"Elapsed time: 985.379787 msecs"
point-to-hilbert-let-from-global nil

--
Michael Wood <esio...@gmail.com>

[John Harrop]

Interesting. It looks like Clojure's missing a few obvious optimizations, and is reconstructing the literal structure each time the function is called, or each time the value is used if the literal is directly at point of use.

On the other hand, deref of a global is not exactly blindingly fast either, since it uses Java ThreadLocals under the hood (or equivalent mechanism).

Somewhat surprising performance problems when you consider that a literal data structure should actually be right there in the code, constructed already by the Clojure reader at read-time. I guess when class bytecodes are generated it turns into a set of function calls to vec, list, hash-map &c.

I suggest at least one of these two alternatives be done:

1. Alter the bytecode generator to turn such literals into a static final field whose initializer generates the structure, plus a reference to that field; if identical literal structures recur the same static final field can be referenced for each copy.

2. Add a defconstant* special form: can be redef'd but is otherwise strictly constant; (binding ...) will not work on it, nor set!. This can therefore be stored and accessed more efficiently, without going through ThreadLocal or anything similar and thread-dependent, for higher speed access and greater JIT potential. Add appropriate defconstant and defconstant- macros to core that wrap the special form and add docstring and metadata support.

[Alex Osborne]

ajuc wrote:
> I would like to somehow hide the global hilbert-map into my function,
> but I can't see how to do that.
>
> Is this possible? I know that I can just inert literal into my let,
> but that degrades performance, when function is called many times.
>
> I would like to have something like static local variable in C++, or
> just regular constant local variable in my function.

Clojure's name gives a hint as to how do this: use a closure. :-) Just
pull the let outside the defn:

(let [hilbert-map {...}]
(defn point-to-hilbert [...]
...))

[John Harrop]

Has anyone benchmarked this alternative? 

[Alex Osborne]

John Harrop wrote:
> On Sun, Nov 15, 2009 at 7:32 PM, Alex Osborne <a...@meshy.org
> <mailto:a...@meshy.org>> wrote:
>
> ajuc wrote:
> > I would like to somehow hide the global hilbert-map into my function,
> > but I can't see how to do that.
>

> Clojure's name gives a hint as to how do this: use a closure. :-) Just
> pull the let outside the defn:
>
> (let [hilbert-map {...}]
> (defn point-to-hilbert [...]
> ...))
>
>
> Has anyone benchmarked this alternative?

On my PC it's indistinguishable from point-to-hilbert-let-from-global
and point-to-hilbert-directly-from-global. I get around 750ms +- 20ms
for all three of them (after letting the JIT warm up by running a few
times).

[ajuc]

On 16 Lis, 01:32, Alex Osborne <a...@meshy.org> wrote:
> Clojure's name gives a hint as to how do this: use a closure. :-)  Just
> pull the let outside the defn:
>
> (let [hilbert-map {...}]
>    (defn point-to-hilbert [...]
>      ...))

Now it seems so obvious :).
I guess I don't think functional yet.
Thank you, that's exactly what I was trying to achieve.

[Rich Hickey]

On Sun, Nov 15, 2009 at 4:49 AM, ajuc <aju...@gmail.com> wrote:
>
>

Maps, vectors etc are evaluated. This is an important feature, as it
allows you to e.g. create a vector by saying [x y], where x and y are
non-constants.

If you want a data structure to be unevaluated, then just quote it:

'{ :a {[0 0] [0 :d], ...}

Rich

[John Harrop]

I should have thought of that.

But I was thinking that when the data structure does contain only constants, the compiler could do something like this for you.

Even if you have e.g.

[[1 2] [x 4]]

the [1 2] part is unvarying and the resulting bytecode could be roughly equivalent to (vector '[1 2] (vector x 4)).

In other words, basically just treat as quoted everything that won't change in meaning by quoting it. The decision algorithm is basically

(defn data-structure? [x]

  (or (map? x) (set? x) (vector? x)))

(defn data? [x]

  (if (data-structure? x)

    (every? data? x)

    (or (number? x) (string? x) (keyword? x) (instance? Character x))))

though it might be useful to extend it to (list a b c) forms that evaluate to static lists by effectively transforming these to '(a b c) as well. (Probably less important, as one usually uses ' as a shortcut when creating a constant list anyway. But cluttering up your vectors and maps with 's to speed things up seems both ugly and avoidable with a few more compiler optimization smarts.)