Magic incantations and immutable arrays

77 views
Skip to first unread message

Toivo Henningsson

unread,
Apr 26, 2012, 4:30:34 AM4/26/12
to julia-dev
I would like to bring up a subject that I feel has been left out from
the discussion on delayed evaluation so far: immutable arrays.
My starting point is the fact that delayed evaluation needs the
operands' values to remain constant from delay to evaluation.

Now, this is not a problem for lesser magic like

X = @kernel A.*B + C

since the magic is confined to the @kernel block, which has no
assignments to A, B, C anyway.

But I can't escape the conclusion that immutable arrays are necessary
to do greater magic,
i e evaluation that is delayed for a yet unknown length of time.

Personally, I'd be content with lesser magic for a good while yet, but
I still want to ask the question:
Should there be an immutable array type in Julia?
(And how should it work? Be implemented? Interact with the rest of the
system? ...)

Given that greater magic requires immutable data,
how do people feel about having the reverse implication:
Take immutable data (or at least immutable arrays) as a license to do
greater magic.

Any thoughts?

/ Toivo

Stefan Karpinski

unread,
Apr 26, 2012, 5:03:18 AM4/26/12
to juli...@googlegroups.com
If this kind of kernel requires immutable arrays, I would generally recommend not mutating your arrays while performing such magic :-)

Toivo Henningsson

unread,
Apr 26, 2012, 5:20:36 AM4/26/12
to julia-dev


On Apr 26, 11:03 am, Stefan Karpinski <ste...@karpinski.org> wrote:
> If this kind of kernel requires immutable arrays, I would generally
> recommend not mutating your arrays while performing such magic :-)

Definitely. And you don't: there's no other operations intervening
while X = @kernel A.*B + C is executed.

What I'm talking about is a case like when you create some data in an
array, and then pass it around to accumulate delayed evaluation steps
in various parts of the code.
You might call it dynamically delayed evaluation since the system
creates kernels depending on the history of your data objects,
as opposed statically delayed evaluation like X = @kernel A.*B + C
where the programmer delimits the maximum delay explicitly.

I know there's a bit of a divide between those who want to do
dynamically delayed evaluation, and those who prefer statically
delayed evalutation since it's simpler and more explicit.
I personally like the static case, and I feel that it's best to start
with simple things first.
But I still think that having an immutable array type integrated into
Julia might make a big difference performance-wise at some point in
the future, so I wanted to ask the question now.

david tweed

unread,
Apr 26, 2012, 7:32:48 AM4/26/12
to julia-dev
On Apr 26, 10:20 am, Toivo Henningsson <toivo....@gmail.com> wrote:
> On Apr 26, 11:03 am, Stefan Karpinski <ste...@karpinski.org> wrote:
>
> > If this kind of kernel requires immutable arrays, I would generally
> > recommend not mutating your arrays while performing such magic :-)
>
> Definitely. And you don't: there's no other operations intervening
> while X = @kernel A.*B + C is executed.
>
> What I'm talking about is a case like when you create some data in an
> array, and then pass it around to accumulate delayed evaluation steps
> in various parts of the code.
> You might call it dynamically delayed evaluation since the system
> creates kernels depending on the history of your data objects,
> as opposed statically delayed evaluation like X = @kernel A.*B + C
> where the programmer delimits the maximum delay explicitly.

One other potential reason for having immutability would be
parallelisation: if you know an array is immutable then, once it's
been created, you can duplicate it on participating NUMA node/machines
safely.

> I know there's a bit of a divide between those who want to do
> dynamically delayed evaluation, and those who prefer statically
> delayed evalutation since it's simpler and more explicit.
> I personally like the static case, and I feel that it's best to start
> with simple things first.
> But I still think that having an immutable array type integrated into
> Julia might make a big difference performance-wise at some point in
> the future, so I wanted to ask the question now.

FWIW, my interest falls into a third class. The kind of optimisation
I'd like to do is "statically compiling" a function into a version
which is faster, but with the expectation that the typical programmer
will use a wide array of constructs which won't have delayed-evalution
implementations (from the sheer volume of work).

The particular use case I care about is that lots of the time in an
IDE with a language like Matlab, it's common to end up repeatedly
selecting the same block of code and evaluating it (with the inputs
having been changed in-between). It always annoys me when after the
tenth time it's still taking 5 seconds when it could be being run in
1s if the system would just do some analysis. In this case you want
the minimum anotation of the source. Since Julia encourages small
functions, the function level seems like a basic-unit to imlement this
at.

Krzysztof Kamieniecki

unread,
Apr 26, 2012, 8:56:55 AM4/26/12
to juli...@googlegroups.com
I am voting for immutable arrays, it makes it easier to implement what the user wants to do

For instance calling X := X[remix] .^ A + B without complex work this requires that the result X is a new block of memory (With the hit of allocating (I will probably have a horde of temporaries), and possible cache performance problems)

I view these operations as working on arrays that are values and not collections of values. I think in most cases the code will be changing a lot of elements per operation

I think most people will use the library in a single threaded mode (where there will not be multiple user created threads trying to change the same values). It seems that in that case there is no user visible difference (ignore watching CPU usage etc...) between static and dynamic.

Peder Axensten

unread,
Apr 26, 2012, 1:26:21 PM4/26/12
to juli...@googlegroups.com
A swap function?
Put the calculation results into a temporary and then swap (references, not values) X and temp -- the old X values vanishes when temp goes out of scope.

Hälsar Peder

Krzysztof Kamieniecki

unread,
Apr 26, 2012, 2:15:53 PM4/26/12
to juli...@googlegroups.com
Yes I did mean swapping the references.

My sentence should have read "For instance calling X := X[remix] .^ A + B without some complex work coding on the part of the library requires that the result X is a new block of memory (With the hit of allocating (I will probably have a horde of temporaries), and possible cache performance problems)"


On Thursday, April 26, 2012 1:26:21 PM UTC-4, Peder Axensten wrote:
A swap function?
Put the calculation results into a temporary and then swap (references, not values) X and temp -- the old X values vanishes when temp goes out of scope.

Hälsar Peder

Toivo Henningsson

unread,
Apr 26, 2012, 4:23:17 PM4/26/12
to julia-dev
On Apr 26, 11:03 am, Stefan Karpinski <ste...@karpinski.org> wrote:
> If this kind of kernel requires immutable arrays, I would generally
> recommend not mutating your arrays while performing such magic :-)

Now that I think about it, complete immutability might be a bit too
harsh.
It would probably be better for me to denote an Array as frozen for
some interval of time.
This of course requires some care from the programmer, but that's
maybe not such an unreasonable thing to demand as I first thought :)

If anyone's interested, I made a small sketch here:
https://gist.github.com/2502738

The idea is to do
A = freeze(A)
# A is now a Frozen{Array} that holds the original A
do stuff...
A = unfreeze(A) # notify all interested and return original A

or equivalently

@freeze A begin
do stuff...
end

Stefan Karpinski

unread,
Apr 26, 2012, 4:26:06 PM4/26/12
to juli...@googlegroups.com
Definitely like the block version better. But I kind of figure why separate the freezing from the indication that you want to do the kinds of transformations that require frozen arrays?

Patrick O'Leary

unread,
Apr 26, 2012, 4:35:44 PM4/26/12
to juli...@googlegroups.com

This looks like a concurrency problem waiting to happen, unless I'm missing something.

david tweed

unread,
Apr 26, 2012, 5:20:47 PM4/26/12
to julia-dev
I'm not sure about the notion of temporarily freezing arrays: I
suspect it might be something that's too much work for quick
prototyping and not fine-grained enough for performance critical
production stuff. However, I suspect the only way to know is to try it
and see...

Minor point: It would be really nice if the freezing syntax didn't
need another "end" in the code: I know it's a C++-ish idiom but I'd
prefer creating some object that freezes some set of arrays until the
end of the current scope, linking the unfreezing to running the
finalisation. (There's almost certainly another natural scope co-
inciding with the time that freezing is appropriate.)

Toivo Henningsson

unread,
Apr 28, 2012, 8:15:29 AM4/28/12
to julia-dev


On Apr 26, 10:26 pm, Stefan Karpinski <ste...@karpinski.org> wrote:
> Definitely like the block version better.

Yeah, me too. The more I think about it, the more it feels better:
simpler, easier to understand what's happening, less that can go
wrong...

> But I kind of figure why separate
> the freezing from the indication that you want to do the kinds of
> transformations that require frozen arrays?

My thought was that it is the owner of an Array that decides to freeze
it,
and users of the Array that want it frozen and have a common place to
store a reference to themselves so that they can be notified before
the owner decides to unfreeze.
But yeah, this far more complicated than necessary for anything I can
think of right now :)
Reply all
Reply to author
Forward
0 new messages