Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > To increase speed on manipulating big arrays in Java with minimal bounds checking, ...

Reply
Thread Tools

To increase speed on manipulating big arrays in Java with minimal bounds checking, ...

 
 
Casey Hawthorne
Guest
Posts: n/a
 
      08-31-2005
To increase speed on manipulating big arrays in Java with minimal
bounds checking, would it be possible to have some operators that only
do bounds checking at the boundaries of the array?

I suppose I'm thinking of some sort of 2D or 3D (or more) iterator?

Maybe some sort of APL like functions?
--
Regards,
Casey
 
Reply With Quote
 
 
 
 
Chris Uppal
Guest
Posts: n/a
 
      08-31-2005
Casey Hawthorne wrote:

> To increase speed on manipulating big arrays in Java with minimal
> bounds checking, would it be possible to have some operators that only
> do bounds checking at the boundaries of the array?


You could always write custom array operations in JNI. Otherwise the answer is
no (not without a change to the JVM design, which isn't going to happen).

OTOH, it is /said/ (I find it plausible, but I can't confirm it from personal
knowledge) that the big name JVM's JITers are pretty aggressive about removing
bounds checks in the generated code, so there might not be much to gain from
special operators.

-- chris



 
Reply With Quote
 
 
 
 
Thomas Hawtin
Guest
Posts: n/a
 
      08-31-2005
Casey Hawthorne wrote:
> To increase speed on manipulating big arrays in Java with minimal
> bounds checking, would it be possible to have some operators that only
> do bounds checking at the boundaries of the array?


A good runtime will pull bounds checking out of inner loops.

This sort of low level optimisation is not something to be concerned about.

Tom Hawtin
--
Unemployed English Java programmer
http://jroller.com/page/tackline/
 
Reply With Quote
 
Robert Klemme
Guest
Posts: n/a
 
      08-31-2005
Chris Uppal wrote:
> Casey Hawthorne wrote:
>
>> To increase speed on manipulating big arrays in Java with minimal
>> bounds checking, would it be possible to have some operators that
>> only do bounds checking at the boundaries of the array?

>
> You could always write custom array operations in JNI. Otherwise the
> answer is no (not without a change to the JVM design, which isn't
> going to happen).


I'm not sure whether array accesses via JNI actually bypass bounds checks.
You probably would have to copy the Java array into a native array,
perform the algorithm on it and copy results back. This sounds quite
imperformant to me.

> OTOH, it is /said/ (I find it plausible, but I can't confirm it from
> personal knowledge) that the big name JVM's JITers are pretty
> aggressive about removing bounds checks in the generated code, so
> there might not be much to gain from special operators.


Also: what do you gain by a specific operator to be used on boundaries?
If you *know* you're at a boundary why then even bother to check? Bounds
checking is there to prevent accidental violations - something that would
lead to undefined behavior or even crashes if omitted.

Kind regards

robert

 
Reply With Quote
 
Chris Uppal
Guest
Posts: n/a
 
      08-31-2005
Robert Klemme wrote:

> > [me]
> > You could always write custom array operations in JNI. Otherwise the
> > answer is no (not without a change to the JVM design, which isn't
> > going to happen).

>
> I'm not sure whether array accesses via JNI actually bypass bounds checks.


It does. The way the JNI interfaces work (for arrays of primitive types --
which are the only kind worth considering in this context) the API gives you
(at its choice) either a pointer to the data (which you have to return
explicitly) or a pointer to a temporary copy of the data (which you also have
to return). In either case access to the individual elements is at full memory
speed. There is no need to issue a JNI call for each array access.

Also note that it is very unlikely that the overhead of copying (if it happens
at all) would matter. Copying is O(n), but unless the operation itself were
significantly more expensive than O(n) there would be no point in optimising
it.

-- chris


 
Reply With Quote
 
Chris Uppal
Guest
Posts: n/a
 
      08-31-2005
Thomas Hawtin wrote:

> This sort of low level optimisation is not something to be concerned
> about.


Unless, of course, you are manipulating large amounts of data and the
application is running too[*] slow.

Which is a perfectly reasonable scenario.

-- chris

([*] for any of several possible values of "too", eg:
- three times slower than the legacy application we are trying to replace.
- it takes a week to run, but we need to run it once per day.
- it takes 120 millisecs to run, but I need to refresh the frame 25
times/second.
- it takes several hours to run, so any significant speedup would be useful
- ...
)




 
Reply With Quote
 
Thomas Hawtin
Guest
Posts: n/a
 
      08-31-2005
Chris Uppal wrote:
> Thomas Hawtin wrote:
>
>>This sort of low level optimisation is not something to be concerned
>>about.

>
> Unless, of course, you are manipulating large amounts of data and the
> application is running too[*] slow.
>
> Which is a perfectly reasonable scenario.


I'd start at oprimisations that reduce the amount of data involved and
accesses to it, rather than focus on some kind of made up worries.

Tom Hawtin

> ([*] for any of several possible values of "too", eg:
> - three times slower than the legacy application we are trying to

replace.
> - it takes a week to run, but we need to run it once per day.
> - it takes 120 millisecs to run, but I need to refresh the frame 25
> times/second.
> - it takes several hours to run, so any significant speedup would

be useful
> - ...
> )


I'm not seeing how array bounds checking comes into this. This kind of
optimisation is handled by the runtime.
--
Unemployed English Java programmer
http://jroller.com/page/tackline/
 
Reply With Quote
 
Patricia Shanahan
Guest
Posts: n/a
 
      08-31-2005
Chris Uppal wrote:
> Thomas Hawtin wrote:
>
>
>>This sort of low level optimisation is not something to be concerned
>>about.

>
>
> Unless, of course, you are manipulating large amounts of data and the
> application is running too[*] slow.


and you have investigated the slowness and found that it is due to
bounds checking.

>
> Which is a perfectly reasonable scenario.
>
> -- chris
>
> ([*] for any of several possible values of "too", eg:
> - three times slower than the legacy application we are trying to replace.
> - it takes a week to run, but we need to run it once per day.
> - it takes 120 millisecs to run, but I need to refresh the frame 25
> times/second.
> - it takes several hours to run, so any significant speedup would be useful
> - ...
> )
>
>
>
>

 
Reply With Quote
 
Robert Klemme
Guest
Posts: n/a
 
      08-31-2005
Chris Uppal wrote:
> Robert Klemme wrote:
>
>>> [me]
>>> You could always write custom array operations in JNI. Otherwise
>>> the answer is no (not without a change to the JVM design, which
>>> isn't going to happen).

>>
>> I'm not sure whether array accesses via JNI actually bypass bounds
>> checks.

>
> It does. The way the JNI interfaces work (for arrays of primitive
> types -- which are the only kind worth considering in this context)
> the API gives you (at its choice) either a pointer to the data (which
> you have to return explicitly) or a pointer to a temporary copy of
> the data (which you also have to return). In either case access to
> the individual elements is at full memory speed. There is no need to
> issue a JNI call for each array access.


Ah, thanks for the heads up.

> Also note that it is very unlikely that the overhead of copying (if
> it happens at all) would matter. Copying is O(n), but unless the
> operation itself were significantly more expensive than O(n) there
> would be no point in optimising it.


Erm, strictly speaking copying becomes relatively cheaper (and thus
neglectible) if the op is worse than O(n), doesn't it? Anyway, even if
the op is O(n) you could neglect copying - from a theoretical perspective
(O(n) = O(2n)). It might be different in practice if arrays are huge (mem
allocation overhead) or if they are small and there are many invocations.

Kind regards

robert

 
Reply With Quote
 
TechBookReport
Guest
Posts: n/a
 
      08-31-2005
Casey Hawthorne wrote:
> To increase speed on manipulating big arrays in Java with minimal
> bounds checking, would it be possible to have some operators that only
> do bounds checking at the boundaries of the array?
>
> I suppose I'm thinking of some sort of 2D or 3D (or more) iterator?
>
> Maybe some sort of APL like functions?
> --
> Regards,
> Casey


If you're looking for commercial solutions then SmartArrays might be of
interest. It's very APL-like and supports Java and .NET, from what I've
read in the past. The authors have a long history of development of APL
interpreters and systems.

--
TechBookReport Java book reviews:
http://www.techbookreport.com/JavaIndex.html

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
GIDS 2009 .Net:: Save Big, Win Big, Learn Big: Act Before Dec 29 2008 Shaguf ASP .Net 0 12-26-2008 09:29 AM
GIDS 2009 .Net:: Save Big, Win Big, Learn Big: Act Before Dec 29 2008 Shaguf ASP .Net Web Controls 0 12-26-2008 06:11 AM
GIDS 2009 Java:: Save Big, Win Big, Learn Big: Act Before Dec 29 2008 Shaguf Python 0 12-24-2008 07:35 AM
GIDS 2009 Java:: Save Big, Win Big, Learn Big: Act Before Dec 29 2008 Shaguf Ruby 0 12-24-2008 05:07 AM
Bounds checked arrays jacob navia C Programming 50 02-23-2004 02:55 AM



Advertisments