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

Discussion in 'Java' started by Casey Hawthorne, Aug 31, 2005.

  1. 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
    Casey Hawthorne, Aug 31, 2005
    #1
    1. Advertising

  2. Casey Hawthorne

    Chris Uppal Guest

    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
    Chris Uppal, Aug 31, 2005
    #2
    1. Advertising

  3. Re: To increase speed on manipulating big arrays in Java with minimalbounds checking, ...

    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/
    Thomas Hawtin, Aug 31, 2005
    #3
  4. 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
    Robert Klemme, Aug 31, 2005
    #4
  5. Casey Hawthorne

    Chris Uppal Guest

    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
    Chris Uppal, Aug 31, 2005
    #5
  6. Casey Hawthorne

    Chris Uppal Guest

    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
    - ...
    )
    Chris Uppal, Aug 31, 2005
    #6
  7. Re: To increase speed on manipulating big arrays in Java with minimalbounds checking, ...

    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/
    Thomas Hawtin, Aug 31, 2005
    #7
  8. Re: To increase speed on manipulating big arrays in Java with minimalbounds checking, ...

    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
    > - ...
    > )
    >
    >
    >
    >
    Patricia Shanahan, Aug 31, 2005
    #8
  9. 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
    Robert Klemme, Aug 31, 2005
    #9
  10. Re: To increase speed on manipulating big arrays in Java with minimalbounds checking, ...

    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
    TechBookReport, Aug 31, 2005
    #10
  11. Re: To increase speed on manipulating big arrays in Java with minimalbounds checking, ...

    Robert Klemme wrote:
    ....
    >
    > 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.

    ....

    For any finite problem size, O(n) can be worse than O(n^2).

    Patricia
    Patricia Shanahan, Aug 31, 2005
    #11
  12. Patricia Shanahan wrote:
    > Robert Klemme wrote:
    > ...
    >>
    >> 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. ...

    >
    > For any finite problem size, O(n) can be worse than O(n^2).


    Does the term O(n) make sense for finite problems? Big O is just about
    asymptotic values. And, yes, as I said, in practice the overhead may
    indeed count. :)

    Kind regards

    robert
    Robert Klemme, Aug 31, 2005
    #12
  13. Casey Hawthorne

    Chris Uppal Guest

    Patricia Shanahan 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.


    I think you have misunderstood me. I was talking about the circumstances under
    which one would get into that kind of investigation in the first place, not the
    circumstances under which one would actually attempt to optimise. As you say,
    there's no point in optimising something that isn't actually slowing you
    down[*].

    ([*] Although I should add that quite often the simplest way of measuring the
    potential gains from an optimisation is just to try it, or a simplified
    version of it)

    -- chris
    Chris Uppal, Aug 31, 2005
    #13
  14. Re: To increase speed on manipulating big arrays in Java with minimalbounds checking, ...

    Hi,

    Robert Klemme wrote:
    >>For any finite problem size, O(n) can be worse than O(n^2).

    >
    > Does the term O(n) make sense for finite problems?


    Of course:

    > Big O is just about
    > asymptotic values.


    Yes. But most (or even all?) algorithms are defined to *theoretically*
    run with an unlimited 'n', although *in practise*, 'n' is always finite,
    i.e. limited and not 'infinity'.

    > And, yes, as I said, in practice the overhead may
    > indeed count. :)


    That's it!

    Ciao,
    Ingo
    Ingo R. Homann, Aug 31, 2005
    #14
  15. Ingo R. Homann wrote:
    > Hi,
    >
    > Robert Klemme wrote:
    >>> For any finite problem size, O(n) can be worse than O(n^2).

    >>
    >> Does the term O(n) make sense for finite problems?

    >
    > Of course:
    >
    >> Big O is just about
    >> asymptotic values.

    >
    > Yes. But most (or even all?) algorithms are defined to *theoretically*
    > run with an unlimited 'n', although *in practise*, 'n' is always
    > finite, i.e. limited and not 'infinity'.


    Yep, but in that case you can't work with O but you have to be more
    specific (i.e. know the constants). That's why IMHO it doesn't make sense
    here - at least you'll have to take O's with a grain of salt and look a
    bit closer.

    >> And, yes, as I said, in practice the overhead may
    >> indeed count. :)

    >
    > That's it!


    Yepp, think we agree here. Just wanted to make the distinction clear.

    robert
    Robert Klemme, Aug 31, 2005
    #15
  16. Casey Hawthorne

    Roedy Green Guest

    On Wed, 31 Aug 2005 08:19:55 GMT, Casey Hawthorne
    <> wrote or quoted :

    >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?


    Only in theory is every reference bounds checked. The JVM is free to
    check the bounds at the beginning of a loop to make sure there cannot
    possibly be trouble.

    for (String s : stringarray )
    has no index to check in the loop.

    In Jet you can turn off some checking, possibly bound checks, but not
    in any Sun JVM.


    --
    Canadian Mind Products, Roedy Green.
    http://mindprod.com Again taking new Java programming contracts.
    Roedy Green, Aug 31, 2005
    #16
  17. Casey Hawthorne

    Guest

    Roedy Green wrote:
    > On Wed, 31 Aug 2005 08:19:55 GMT, Casey Hawthorne
    > <> wrote or quoted :
    >
    > >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?

    >
    > In Jet you can turn off some checking, possibly bound checks, but not
    > in any Sun JVM.


    This feature will be disabled in Excelsior JET 4.0 as it is not
    compliant with the Java spec. But sophisticated JVMs like Sun HotSpot,
    BEA JRockit or Excelsior JET remove bounds checking when it is possible
    to compute the range of the index expression before execution. So what
    you should do is you should write your code so that the JVM can compute
    those ranges (and also determine whether objects and arrays used in a
    loop are not null before the loop.)

    LDV
    , Sep 1, 2005
    #17
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Casey Hawthorne
    Replies:
    21
    Views:
    868
    Roedy Green
    Jun 5, 2004
  2. Shaguf
    Replies:
    0
    Views:
    346
    Shaguf
    Dec 24, 2008
  3. Shaguf
    Replies:
    0
    Views:
    443
    Shaguf
    Dec 26, 2008
  4. Shaguf
    Replies:
    0
    Views:
    229
    Shaguf
    Dec 26, 2008
  5. Shaguf
    Replies:
    0
    Views:
    211
    Shaguf
    Dec 24, 2008
Loading...

Share This Page