On Sat, Apr 4, 2009 at 7:28 AM,
<address@hidden> wrote:
Send Help-octave mailing list submissions to
address@hidden
To subscribe or unsubscribe via the World Wide Web, visit
https://www-old.cae.wisc.edu/mailman/listinfo/help-octave
or, via email, send a message with subject or body 'help' to
address@hidden
You can reach the person managing the list at
address@hidden
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Help-octave digest..."
Today's Topics:
1. Re: Performance optimization (allocation inside a for loop)
(Przemek Klosowski)
2. Re: Color of scatter? (Rob Mahurin)
3. Re: Performance optimization (allocation inside a for loop)
(Rob Mahurin)
4. Re: Color of scatter? (David Bateman)
5. creating an matrix from C++ array (Martijn)
6. Re: Performance optimization (allocation inside a for loop)
(Jaroslav Hajek)
7. Re: creating an matrix from C++ array (Jaroslav Hajek)
8. Re: Performance optimization (allocation inside a for loop) (r)
----------------------------------------------------------------------
Message: 1
Date: Fri, 3 Apr 2009 14:39:26 -0400 (EDT)
From: Przemek Klosowski <address@hidden>
Subject: Re: Performance optimization (allocation inside a for loop)
To: address@hidden
Message-ID: <address@hidden>
Is it possible to adjust the Octave's allocation algorithm so that it
could allocate larger chunks of data (or growing chunks of data)?
The common way of doing what you're asking is to over-allocate,
e.g. on filling up the current size-N block, re-allocate a new block of
size 2N; this way the allocation and copying cost is proportional to
the log(size) rather than size of the array.
The problem for Octave is that it results in wasting a constant
fraction of the total allocated size, which is a critical no-no for
anyone with large data sets.
I wonder if the allocation algorithm could be modified to
over-allocate a constant _amount_ (rather than constant fraction)---or
maybe a constant fraction up to certain array size and constant amount
above that. Of course this approach would require arrays to have two
sizes: user-visible and internal---because we don't want the
over-allocation to be shown in length(array)
------------------------------
Message: 2
Date: Fri, 3 Apr 2009 15:22:32 -0400
From: Rob Mahurin <address@hidden>
Subject: Re: Color of scatter?
To: David Doria <address@hidden>
Cc: address@hidden
Message-ID: <address@hidden>
Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed
On Mar 31, 2009, at 11:35 AM, David Doria wrote:
> I would expect this to produce a red marker at (1,1). It is, however,
> green. Am I mis-interpreting the syntax? The red marker is what I
> see in
> matlab.
>
> scatter(1,1,[],[1 0 0])
I see a red marker with octave 3.0.3, but a green marker in a recent
development version. I don't know enough to track down the bug, though.
Cheers,
Rob
--
Rob Mahurin
Department of Physics and Astronomy
University of Tennessee 865 207 2594
Knoxville, TN 37996 address@hidden
------------------------------
Message: 3
Date: Fri, 3 Apr 2009 15:49:11 -0400
From: Rob Mahurin <address@hidden>
Subject: Re: Performance optimization (allocation inside a for loop)
To: address@hidden
Message-ID: <address@hidden>
Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed
On Apr 3, 2009, at 2:39 PM, Przemek Klosowski wrote:
>> Is it possible to adjust the Octave's allocation algorithm so
>> that it could allocate larger chunks of data (or growing chunks of
>> data)?
>
>
> The common way of doing what you're asking is to over-allocate,
> e.g. on filling up the current size-N block, re-allocate a new
> block of size 2N; this way the allocation and copying cost is
> proportional to the log(size) rather than size of the array.
>
> The problem for Octave is that it results in wasting a constant
> fraction of the total allocated size, which is a critical no-no for
> anyone with large data sets.
>
> I wonder if the allocation algorithm could be modified to over-
> allocate a constant _amount_ (rather than constant fraction)---or
> maybe a constant fraction up to certain array size and constant
> amount above that. Of course this approach would require arrays to
> have two sizes: user-visible and internal---because we don't want
> the over-allocation to be shown in length(array)
One solution might be to allocate the requested amount of memory on
creation, and use some over-allocation if the (end+1)th element is
accessed. Then code like
list = []; for i = 1:n; list(i) = something; endfor
would have some-but-fewer reallocations, while
data = "" huge enormous]);
for i = 1:numel(data); data(i) = something; endfor
wouldn't have a space penalty.
This sort of under-the-carpet trickiness would still lead to subtle
bugs, but different ones from a reallocation for every size change.
Another option would be to have an internal counter associated with a
matrix that counts how many times it's been reallocated, and switches
strategies (perhaps emitting a warning) if the same object's size
increases by the same amount more than a handful of times.
Rob
--
Rob Mahurin
Department of Physics and Astronomy
University of Tennessee 865 207 2594
Knoxville, TN 37996 address@hidden
------------------------------
Message: 4
Date: Fri, 03 Apr 2009 22:27:28 +0200
From: David Bateman <address@hidden>
Subject: Re: Color of scatter?
To: Rob Mahurin <address@hidden>
Cc: address@hidden, David Doria <address@hidden>
Message-ID: <address@hidden>
Content-Type: text/plain; charset="iso-8859-1"
Rob Mahurin wrote:
> On Mar 31, 2009, at 11:35 AM, David Doria wrote:
>
>> I would expect this to produce a red marker at (1,1). It is, however,
>> green. Am I mis-interpreting the syntax? The red marker is what I
>> see in
>> matlab.
>>
>> scatter(1,1,[],[1 0 0])
>>
>
>
> I see a red marker with octave 3.0.3, but a green marker in a recent
> development version. I don't know enough to track down the bug, though.
>
> Cheers,
> Rob
>
>
Does the attached changeset fix the issue? The problem as I see it was
that the creation of a matlab compatible scatter group required that
each point in the scatter plot was a separate patch. The indexing into
the cdata values was incorrect for a fixed color as a three element
vector like you gave.
D.
--
David Bateman address@hidden
35 rue Gambetta +33 1 46 04 02 18 (Home)
92100 Boulogne-Billancourt FRANCE +33 6 72 01 06 33 (Mob)
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: patch.scatter
Url: https://www-old.cae.wisc.edu/pipermail/help-octave/attachments/20090403/ca9cb7fb/attachment-0001.ksh
------------------------------
Message: 5
Date: Sat, 04 Apr 2009 08:31:42 +0200
From: Martijn <address@hidden>
Subject: creating an matrix from C++ array
To: address@hidden
Message-ID: <address@hidden>
Content-Type: text/plain
Hi,
I would like to create an octave matrix (of uint16) from an C++ array,
but there is apparently no constructor that accepts this:
unsigned a[11];
for(int i=0; i<11; i++)
{ a[i]=i;
}
uint16NDArray A(a,11);
Do I have to loop over all elements or is there a quicker way?
I want to used such construction to read a lot of uint16 data from a
file into an C++ array of unsigned shorts. Then I would like to create
an octave uint16NDArray from the array.
with kind regards,
Martijn
------------------------------
Message: 6
Date: Sat, 4 Apr 2009 08:47:03 +0200
From: Jaroslav Hajek <address@hidden>
Subject: Re: Performance optimization (allocation inside a for loop)
To: "John W. Eaton" <address@hidden>
Cc: address@hidden
Message-ID:
<address@hidden>
Content-Type: text/plain; charset="iso-8859-1"
On Thu, Apr 2, 2009 at 10:06 PM, John W. Eaton <address@hidden> wrote:
> On ?2-Apr-2009, r wrote:
>
> | I think chunks of ~5% of the structure size (perhaps more for smaller
> | arrays) would be affordable by anyone and would effectively fix these
> | allocation issues in practical applications. Whether it is worth the
> | effort is a different question.
>
> If you think this is important, how about submitting a patch?
>
> jwe
>
I gave the idea a second thought - maybe it has some merits. Sometimes
you really want to use an array as a stack in Octave to avoid going
through a loop twice, so Octave can try to optimize such usage.
For everyone interested, try the attached patch.
Summary: The operations
array(end+1) = something (push)
and
array(end) = [] (pop)
are optimized (the usage of "end" is not necessary), reusing the
existing mechanism for shallow slices.
When a "push" operation is detected, existing over-allocated space
will be reused if possible, otherwise a new array will be
over-allocated twice or by 1024 elements, whichever is smaller. The
"pop" operation simply adjusts the array size.
Since the existing shallow slicing mechanism is reused, no extra data
is introduced. Also, economization will happen as with orphaned
shallow slices, so that the array will be automatically stripped off
any possible over-allocated space when you store it into a variable,
cell or struct element, or return it from a function.
Hence the dangling memory will normally only exist locally.
To facilitate this change, economization no longer happens on every
assignment (which is probably not important anyway).
Here's a simple benchmark:
tic;
for i = 1:1e5
a(i) = i;
endfor
toc
a = [];
tic;
for i = 1:1e5
a(i) = i;
a(i) = [];
a(i) = i+1;
endfor
toc
with recent tip:
Elapsed time is 11.0845 seconds.
Elapsed time is 16.2406 seconds.
with current patch:
Elapsed time is 0.380752 seconds.
Elapsed time is 1.01877 seconds.
a final question: maybe the maximum over-allocation size should be configurable?
enjoy!
--
RNDr. Jaroslav Hajek
computing expert & GNU Octave developer
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz
-------------- next part --------------
A non-text attachment was scrubbed...
Name: stack.diff
Type: text/x-diff
Size: 2871 bytes
Desc: not available
Url : https://www-old.cae.wisc.edu/pipermail/help-octave/attachments/20090404/83bc6f99/attachment-0001.bin
------------------------------
Message: 7
Date: Sat, 4 Apr 2009 09:23:45 +0200
From: Jaroslav Hajek <address@hidden>
Subject: Re: creating an matrix from C++ array
To: Martijn <address@hidden>
Cc: address@hidden
Message-ID:
<address@hidden>
Content-Type: text/plain; charset=ISO-8859-1
On Sat, Apr 4, 2009 at 8:31 AM, Martijn <address@hidden> wrote:
> Hi,
> I would like to create an octave matrix (of uint16) from an C++ array,
> but there is apparently no constructor that accepts this:
>
> ? ? ? ?unsigned a[11];
> ? ? ? ?for(int i=0; i<11; i++)
> ? ? ? ?{ ? ? ? a[i]=i;
> ? ? ? ?}
> ? ? ? ?uint16NDArray A(a,11);
>
> Do I have to loop over all elements or is there a quicker way?
> I want to used such construction to read a lot of uint16 data from a
> file into an C++ array of unsigned shorts. Then I would like to create
> an octave uint16NDArray from the array.
>
In short, no, there's no such constructor. If you want to avoid
copying the elements, use uint16NDArray to manage your data from the
very start.
regards
--
RNDr. Jaroslav Hajek
computing expert & GNU Octave developer
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz
------------------------------
Message: 8
Date: Sat, 4 Apr 2009 12:28:31 +0100
From: r <address@hidden>
Subject: Re: Performance optimization (allocation inside a for loop)
To: address@hidden
Message-ID:
<address@hidden>
Content-Type: text/plain; charset=windows-1252
On Sat, Apr 4, 2009 at 7:47 AM, Jaroslav Hajek <address@hidden> wrote:
>
> I gave the idea a second thought - maybe it has some merits. Sometimes
> you really want to use an array as a stack in Octave to avoid going
> through a loop twice, so Octave can try to optimize such usage.
Thank you for this work. BTW, I've checked that Matlab 2008 doesn't
indeed optimize such scenario. I'm sorry for the unfair judgement.
> Since the existing shallow slicing mechanism is reused, no extra data
> is introduced.
[...]
> a final question: maybe the maximum over-allocation size should be configurable?
If I understand correctly that this optimization doesn't take any
additional memory comparing to the current version, I wouldn't bother
adding more configuration options.
I tried to give it a try but then I encountered an error when building Octave:
make[3]: Entering directory
`/home/r/Installation/octave/hg_20090404/octave/libcruft/misc'
gcc -c -I/usr/include/freetype2 -fPIC -I. -I../.. -I../../liboctave
-I../../src -I../../libcruft/misc -DHAVE_CONFIG_H -mieee-fp -Wall -W
-Wshadow -g -DDP machar.c -o pic/machar.o
machar.c:2:20: error: config.h: No such file or directory
In file included from f77-fcn.h:27,
from machar.c:8:
quit.h:63: error: expected ?=?, ?,?, ?;?, ?asm? or ?__attribute__?
before ?extern?
quit.h:65: error: expected ?=?, ?,?, ?;?, ?asm? or ?__attribute__?
before ?extern?
quit.h:67: error: expected ?=?, ?,?, ?;?, ?asm? or ?__attribute__?
before ?extern?
quit.h:69: error: expected ?=?, ?,?, ?;?, ?asm? or ?__attribute__?
before ?extern?
quit.h:71: error: expected ?=?, ?,?, ?;?, ?asm? or ?__attribute__?
before ?extern?
quit.h:73: error: expected ?=?, ?,?, ?;?, ?asm? or ?__attribute__?
before ?extern?
quit.h:94: error: expected ?=?, ?,?, ?;?, ?asm? or ?__attribute__?
before ?extern?
quit.h:101: error: expected ?=?, ?,?, ?;?, ?asm? or ?__attribute__?
before ?extern?
quit.h:103: error: expected ?=?, ?,?, ?;?, ?asm? or ?__attribute__?
before ?extern?
quit.h:105: error: expected ?=?, ?,?, ?;?, ?asm? or ?__attribute__?
before ?extern?
quit.h:107: error: expected ?=?, ?,?, ?;?, ?asm? or ?__attribute__?
before ?extern?
quit.h:109: error: expected ?=?, ?,?, ?;?, ?asm? or ?__attribute__?
before ?extern?
quit.h:111: error: expected ?=?, ?,?, ?;?, ?asm? or ?__attribute__?
before ?extern?
quit.h:113: error: expected ?=?, ?,?, ?;?, ?asm? or ?__attribute__?
before ?extern?
quit.h:115: error: expected ?=?, ?,?, ?;?, ?asm? or ?__attribute__?
before ?extern?
In file included from machar.c:8:
f77-fcn.h:79: error: expected ?=?, ?,?, ?;?, ?asm? or ?__attribute__?
before ?extern?
f77-fcn.h:222: error: expected ?=?, ?,?, ?;?, ?asm? or ?__attribute__?
before ?int?
machar.c:380: error: ?F77_FUNC? declared as function returning a function
machar.c: In function ?F77_FUNC?:
machar.c:380: warning: type of ?machar? defaults to ?int?
machar.c:380: warning: type of ?MACHAR? defaults to ?int?
machar.c:398: error: ?eps? undeclared (first use in this function)
machar.c:398: error: (Each undeclared identifier is reported only once
machar.c:398: error: for each function it appears in.)
machar.c:398: error: ?epsneg? undeclared (first use in this function)
machar.c:398: error: ?xmin? undeclared (first use in this function)
machar.c:398: error: ?xmax? undeclared (first use in this function)
machar.c:401: error: ?log10_ibeta? undeclared (first use in this function)
machar.c: At top level:
machar.c:380: warning: unused parameter ?machar?
machar.c:380: warning: unused parameter ?MACHAR?
make[3]: *** [pic/machar.o] Error 1
I guess, this must be some kind of a configuration problem, but where?
$ hg clone http://www.octave.org/hg/octave
$ patch -p1 << ../stack.diff
$ autoconf
$ configure
$ make
Regards,
-r.
------------------------------
_______________________________________________
Help-octave mailing list
address@hidden
https://www-old.cae.wisc.edu/mailman/listinfo/help-octave
End of Help-octave Digest, Vol 37, Issue 8
******************************************