how can i optimize the given below code

Discussion in 'Java' started by programmer.sajjad@gmail.com, Mar 20, 2008.

  1. Guest

    String value="";
    if(value.length() == 0) {
    char data[]=new char[count];
    for(int c=0;c<count;c++){
    data[c]='0';
    }
    value=new String(data);
     
    , Mar 20, 2008
    #1
    1. Advertising

  2. wrote:
    > String value="";
    > if(value.length() == 0) {
    > char data[]=new char[count];
    > for(int c=0;c<count;c++){
    > data[c]='0';
    > }
    > value=new String(data);


    Why do you want to optimize this code? Have you profiled to make sure
    that it is these lines specifically that are the bottleneck?

    If speed really is an issue, then the only thing that jumps out at me
    for optimizing is getting rid of the for loop:

    java.util.Arrays.fill(data, '0');

    --
    Beware of bugs in the above code; I have only proved it correct, not
    tried it. -- Donald E. Knuth
     
    Joshua Cranmer, Mar 20, 2008
    #2
    1. Advertising

  3. Lew Guest

    Joshua Cranmer wrote:
    > wrote:
    >> String value="";
    >> if(value.length() == 0) {
    >> char data[]=new char[count];
    >> for(int c=0;c<count;c++){
    >> data[c]='0';
    >> }
    >> value=new String(data);

    >
    > Why do you want to optimize this code? Have you profiled to make sure
    > that it is these lines specifically that are the bottleneck?
    >
    > If speed really is an issue, then the only thing that jumps out at me
    > for optimizing is getting rid of the for loop:
    >
    > java.util.Arrays.fill(data, '0');


    Is that faster? Enough faster?

    --
    Lew
     
    Lew, Mar 20, 2008
    #3
  4. Eric Sosman Guest

    (It's considered polite to put your question in the body
    of the message, even if it also appears as the Subject.)

    wrote:
    > String value="";
    > if(value.length() == 0) {
    > char data[]=new char[count];
    > for(int c=0;c<count;c++){
    > data[c]='0';
    > }
    > value=new String(data);


    Well, let's see. The original assignment to `value'
    is a waste of time, as is the `if'. Also, `new String(data)'
    will create its own private copy of the `data' array -- it
    must do so, or else you could change the value of the String
    by changing `data' after the String is constructed, so you
    might be better off using a StringBuilder. All in all:

    StringBuilder data = new StringBuilder(count);
    for (int c = 0; c < count; ++c)
    data.append('0');
    String value = data.toString();

    .... and it's hard to believe this would make enough of a
    difference to be worth worrying about.

    --
     
    Eric Sosman, Mar 20, 2008
    #4
  5. Lew wrote:
    > Joshua Cranmer wrote:
    >> wrote:
    >>> String value="";
    >>> if(value.length() == 0) {
    >>> char data[]=new char[count];
    >>> for(int c=0;c<count;c++){
    >>> data[c]='0';
    >>> }
    >>> value=new String(data);

    >>
    >> Why do you want to optimize this code? Have you profiled to make sure
    >> that it is these lines specifically that are the bottleneck?
    >>
    >> If speed really is an issue, then the only thing that jumps out at me
    >> for optimizing is getting rid of the for loop:
    >>
    >> java.util.Arrays.fill(data, '0');

    >
    > Is that faster? Enough faster?
    >


    It may be faster, depending on the system. The only way to tell if it is
    enough faster is for the OP to measure it.

    Many systems have a very fast way of pushing a repeated bit pattern to
    an area of memory. For example, on Sun SPARC systems, 64 byte chunks of
    memory can be written from the floating point registers.

    If the OP's system has some such facility, and Arrays.fill is
    implemented on that system as a native method using an optimized memory
    write method, then it may be significantly faster than than writing one
    char at a time.

    Patricia
     
    Patricia Shanahan, Mar 20, 2008
    #5
  6. Piotr Kobzda Guest

    Patricia Shanahan wrote:
    > Lew wrote:
    >> Joshua Cranmer wrote:
    >>> wrote:
    >>>> String value="";
    >>>> if(value.length() == 0) {
    >>>> char data[]=new char[count];
    >>>> for(int c=0;c<count;c++){
    >>>> data[c]='0';
    >>>> }
    >>>> value=new String(data);
    >>>
    >>> Why do you want to optimize this code? Have you profiled to make sure
    >>> that it is these lines specifically that are the bottleneck?
    >>>
    >>> If speed really is an issue, then the only thing that jumps out at me
    >>> for optimizing is getting rid of the for loop:
    >>>
    >>> java.util.Arrays.fill(data, '0');

    >>
    >> Is that faster? Enough faster?
    >>

    >
    > It may be faster, depending on the system. The only way to tell if it is
    > enough faster is for the OP to measure it.
    >
    > Many systems have a very fast way of pushing a repeated bit pattern to
    > an area of memory. For example, on Sun SPARC systems, 64 byte chunks of
    > memory can be written from the floating point registers.
    >
    > If the OP's system has some such facility, and Arrays.fill is
    > implemented on that system as a native method using an optimized memory
    > write method, then it may be significantly faster than than writing one
    > char at a time.


    You right. However, the reference implementation of Arrays.fill() (I
    mean the one from the Sun) is implemented as a simple loop filling an
    array slot by slot.

    A few years ago I wrote an alternative version of the array fill based
    on System.arraycopy(), which without an extra optimizations normally
    performed by the server JVM is even 5 times faster (sometimes more) than
    the original Arrays.fill() implementation. (The server JVM usually
    still executes it faster, but it's not as significant as in a case of
    the client JVM -- typically not faster than 2 times.)

    The original algorithm is there:
    <http://groups.google.com/group/pl.comp.lang.java/msg/99526c39faf0338c?>
    The thread includes also a performance test driver, and some test
    results. (Sorry, the thread is in Polish. But at least the code should
    be clear for everyone, I hope...)


    piotr
     
    Piotr Kobzda, Mar 20, 2008
    #6
  7. Piotr Kobzda Guest

    Eric Sosman wrote:

    > Also, `new String(data)'
    > will create its own private copy of the `data' array -- it
    > must do so, or else you could change the value of the String
    > by changing `data' after the String is constructed, so you
    > might be better off using a StringBuilder. All in all:
    >
    > StringBuilder data = new StringBuilder(count);
    > for (int c = 0; c < count; ++c)
    > data.append('0');
    > String value = data.toString();


    Is there any benefit of doing it that way?

    There is also a private copy of data array created by the String in this
    case.

    Here is, for example, the StringBuilder's toString() implementation from
    the Sun JDK 1.6:

    public String toString() {
    // Create a copy, don't share the array
    return new String(value, 0, count);
    }

    A data sharing between String and StringBuffer (AFAIK never supported by
    StringBuiledr) was ceased starting Java 1.5.


    piotr
     
    Piotr Kobzda, Mar 20, 2008
    #7
  8. Arne Vajhøj Guest

    wrote:
    > String value="";
    > if(value.length() == 0) {
    > char data[]=new char[count];
    > for(int c=0;c<count;c++){
    > data[c]='0';
    > }
    > value=new String(data);


    If there is a (small) limit on the maximum value of count, then

    value = "0000000000000000000000000000000000000000".substring(0, count);

    may be an alternative.

    Arne
     
    Arne Vajhøj, Mar 20, 2008
    #8
  9. Eric Sosman Guest

    Piotr Kobzda wrote:
    > Eric Sosman wrote:
    >
    >> Also, `new String(data)'
    >> will create its own private copy of the `data' array -- it
    >> must do so, or else you could change the value of the String
    >> by changing `data' after the String is constructed, so you
    >> might be better off using a StringBuilder. [...]

    >
    > A data sharing between String and StringBuffer (AFAIK never supported by
    > StringBuiledr) was ceased starting Java 1.5.


    I wasn't aware of that; thanks for the information.

    I'm still of the opinion, though, that the code fragment
    is almost certainly not worth optimizing.

    --
    Eric Sosman
    lid
     
    Eric Sosman, Mar 21, 2008
    #9
  10. Stefan Ram Guest

    Piotr Kobzda <> writes:
    >A data sharing between String and StringBuffer (AFAIK never
    >supported by StringBuiledr) was ceased starting Java 1.5.


    According to Web sources »StringBuilder« is slightly
    faster than »StringBuffer«, because it does not include
    synchronization.

    Sun Microsystems, Inc. claims:

    »StringBuilder is almost always faster than StringBuffer.«

    http://java.sun.com/j2se/1.5.0/docs/guide/performance/speed.html

    I try to use »java.lang.CharSequence« for text results and
    text parameter types instead of »java.lang.String«, so that
    the »toString()« operation only needs to be invoked when a
    string really is required.
     
    Stefan Ram, Mar 21, 2008
    #10
  11. Lew Guest

    Arne Vajhøj wrote:
    > wrote:
    >> String value="";
    >> if(value.length() == 0) {
    >> char data[]=new char[count];
    >> for(int c=0;c<count;c++){
    >> data[c]='0';
    >> }
    >> value=new String(data);

    >
    > If there is a (small) limit on the maximum value of count, then
    >
    > value = "0000000000000000000000000000000000000000".substring(0, count);
    >
    > may be an alternative.


    One must balance the putative benefit of shaving some microseconds off the
    initialization of 'value' against the risk of increased maintenance difficulty
    concomitant with unobvious code.

    Not that this particular idiom is especially obscure, but it's not a direct
    expression of the algorithm either. Each step further away from the intent,
    be it to optimize or whysoever, requires a little more energy and comment
    density to keep it behaviorally correct.

    This one case is a relatively clear substitution for a nifty, albeit
    insignificant boon in both memory and speed, so it's probably worth it. The
    important thing isn't to reject (relatively) obscure idioms, it's to be
    responsible if you use them.

    If one writes programs to have a long lifespan, it increases the chances that
    they will.

    --
    Lew
     
    Lew, Mar 21, 2008
    #11
  12. Lew wrote:
    > Arne Vajhøj wrote:
    >> wrote:
    >>> String value="";
    >>> if(value.length() == 0) {
    >>> char data[]=new char[count];
    >>> for(int c=0;c<count;c++){
    >>> data[c]='0';
    >>> }
    >>> value=new String(data);

    >>
    >> If there is a (small) limit on the maximum value of count, then
    >>
    >> value = "0000000000000000000000000000000000000000".substring(0, count);
    >>
    >> may be an alternative.

    >
    > One must balance the putative benefit of shaving some microseconds off
    > the initialization of 'value' against the risk of increased maintenance
    > difficulty concomitant with unobvious code.
    >
    > Not that this particular idiom is especially obscure, but it's not a
    > direct expression of the algorithm either. Each step further away from
    > the intent, be it to optimize or whysoever, requires a little more
    > energy and comment density to keep it behaviorally correct.


    I agree about the readability over microoptimization part.

    I find that one line significant easier to read than the loop.

    Completely obvious.

    The only potential drawback is the maximum length needs to be
    a true maximum.

    Arne
     
    Arne Vajhøj, Mar 24, 2008
    #12
  13. Stefan Ram Guest

    "" <> writes:
    >String value="";
    >if(value.length() == 0) {
    > char data[]=new char[count];
    > for(int c=0;c<count;c++){
    > data[c]='0';
    > }
    > value=new String(data);


    This can be written more concise (for count > 0) as:

    String value = String.format( "%0" + count + "d", 0 );

    When count > -1 and count < 5, a faster implementation might be:

    final static String[] v = new String[]{ "", "0", "00", "000", "0000" };
    ....
    value = v[ count ];
     
    Stefan Ram, Mar 24, 2008
    #13
  14. Piotr Kobzda Guest

    Arne Vajhøj wrote:

    >>> If there is a (small) limit on the maximum value of count, then
    >>>
    >>> value = "0000000000000000000000000000000000000000".substring(0, count);
    >>>
    >>> may be an alternative.


    > The only potential drawback is the maximum length needs to be
    > a true maximum.


    Not necessarily. The maximum length limit may be quite easily
    eliminated using longer string when needed. Here is simple realization
    of the idea:

    public class FilledStringGenerator {
    private String source;

    public FilledStringGenerator(String initialSource) {
    if (initialSource == null
    || initialSource.length() == 0)
    throw new IllegalArgumentException();
    this.source = initialSource;
    }

    public String generate(int length) {
    if (length < 0)
    throw new IllegalArgumentException();
    String source = this.source;
    while (source.length() < length)
    this.source = source += source;
    return source.substring(0, length);
    }
    }

    Sample usage:

    FilledStringGenerator fsg = new FilledStringGenerator("0");
    fsg.generate(1);
    fsg.generate(150);
    fsg.generate(70);
    ....

    Thanks to the substring() implementation it generates strings which all
    shares the value array of a longer (or equal) string. (Note however,
    that substring() is not required to always work that way!).


    piotr
     
    Piotr Kobzda, Mar 25, 2008
    #14
  15. Lew Guest

    Piotr Kobzda wrote:
    > Not necessarily. The maximum length limit may be quite easily
    > eliminated using longer string when needed. Here is simple realization
    > of the idea:
    >
    > public class FilledStringGenerator {
    > private String source;
    >
    > public FilledStringGenerator(String initialSource) {
    > if (initialSource == null
    > || initialSource.length() == 0)
    > throw new IllegalArgumentException();
    > this.source = initialSource;
    > }
    >
    > public String generate(int length) {
    > if (length < 0)
    > throw new IllegalArgumentException();
    > String source = this.source;


    Why are you hiding the instance member?

    > while (source.length() < length)
    > this.source = source += source;


    Why are you assigning the string twice each iteration, once to the local
    variable and once to the instance variable?

    > return source.substring(0, length);
    > }
    > }


    This, of courrse, completely kills the OP's stated intention of /optimizing/
    the algorithm.

    --
    Lew
     
    Lew, Mar 25, 2008
    #15
  16. Piotr Kobzda Guest

    Lew wrote:

    >> public class FilledStringGenerator {
    >> private String source;


    >> public String generate(int length) {
    >> if (length < 0)
    >> throw new IllegalArgumentException();
    >> String source = this.source;

    >
    > Why are you hiding the instance member?


    Well, it is not necessary. It just happened during adding simple
    concurrency support to my initial implementation (without changing it).
    Initially the method was operating on the instance variable only.

    >
    >> while (source.length() < length)
    >> this.source = source += source;

    >
    > Why are you assigning the string twice each iteration, once to the local
    > variable and once to the instance variable?


    It's to let access as soon as possible the newly created string by the
    other concurrently running threads.

    Yes, I know, that the Java memory model do not guarantee this (field
    should be volatile to ensure this). But it gives the other threads at
    least a chance to reference a new instance variable still without adding
    the synchronization overheads.

    Note that the assignment to the local is important for the logic, which
    is correct independently of the memory model, i.e. the method will
    always return the correct result.


    >> return source.substring(0, length);
    >> }
    >> }

    >
    > This, of courrse, completely kills the OP's stated intention of
    > /optimizing/ the algorithm.


    Hmmm. Do you think that filling an array char by char and then creating
    a string is more optimal than just creating a substring of the already
    filled string?


    piotr
     
    Piotr Kobzda, Mar 25, 2008
    #16
  17. Lew Guest

    Piotr Kobzda wrote:
    >>> while (source.length() < length)
    >>> this.source = source += source;


    Lew wrote:
    >> Why are you assigning the string twice each iteration, once to the
    >> local variable and once to the instance variable?


    Piotr Kobzda wrote:
    > It's to let access as soon as possible the newly created string by the
    > other concurrently running threads.
    >
    > Yes, I know, that the Java memory model do not guarantee this (field


    In fact, it pretty much guarantees that for some runs, the threads will *not*
    see the changes made by each other.

    > should be volatile to ensure this). But it gives the other threads at
    > least a chance to reference a new instance variable still without adding
    > the synchronization overheads.


    Why would you intentionally do this wrong, i.e., without synchronization? "At
    least a chance"? You're only offering a random chance that the other threads
    can see the changes.

    Never share data between threads without synchronization, unless you really do
    want to get wrong results in order to speed up your code. That really seems
    like a bad tradeoff - programs could be made arbitrarily fast if we didn't
    have that pesky need for correct results.

    You are being very, very foolish.

    --
    Lew
     
    Lew, Mar 26, 2008
    #17
  18. Piotr Kobzda wrote:
    > Arne Vajhøj wrote:
    >>>> If there is a (small) limit on the maximum value of count, then
    >>>>
    >>>> value = "0000000000000000000000000000000000000000".substring(0, count);
    >>>>
    >>>> may be an alternative.

    >
    >> The only potential drawback is the maximum length needs to be
    >> a true maximum.

    >
    > Not necessarily. The maximum length limit may be quite easily
    > eliminated using longer string when needed. Here is simple realization
    > of the idea:
    >
    > public class FilledStringGenerator {
    > private String source;
    >
    > public FilledStringGenerator(String initialSource) {
    > if (initialSource == null
    > || initialSource.length() == 0)
    > throw new IllegalArgumentException();
    > this.source = initialSource;
    > }
    >
    > public String generate(int length) {
    > if (length < 0)
    > throw new IllegalArgumentException();
    > String source = this.source;
    > while (source.length() < length)
    > this.source = source += source;
    > return source.substring(0, length);
    > }
    > }


    But then we again have several lines of code.

    Arne
     
    Arne Vajhøj, Mar 26, 2008
    #18
  19. Piotr Kobzda Guest

    Lew wrote:
    > Piotr Kobzda wrote:
    >>>> while (source.length() < length)
    >>>> this.source = source += source;

    >
    > Lew wrote:
    >>> Why are you assigning the string twice each iteration, once to the
    >>> local variable and once to the instance variable?

    >
    > Piotr Kobzda wrote:
    >> It's to let access as soon as possible the newly created string by the
    >> other concurrently running threads.
    >>
    >> Yes, I know, that the Java memory model do not guarantee this (field

    >
    > In fact, it pretty much guarantees that for some runs, the threads will
    > *not* see the changes made by each other.


    So what? My primary goal was logic validity. Even if some threads
    won't see the changes, they will build their own strings, and the logic
    correctness is preserved.


    >> should be volatile to ensure this). But it gives the other threads at
    >> least a chance to reference a new instance variable still without
    >> adding the synchronization overheads.

    >
    > Why would you intentionally do this wrong, i.e., without
    > synchronization? "At least a chance"? You're only offering a random
    > chance that the other threads can see the changes.


    Because I believe that my "simple approach" is usually faster than
    synchronization, i.e. may be /more optimal/ in some use-cases.


    > Never share data between threads without synchronization, unless you
    > really do want to get wrong results in order to speed up your code.
    > That really seems like a bad tradeoff - programs could be made
    > arbitrarily fast if we didn't have that pesky need for correct results.


    When my approach will give a wrong results?


    >
    > You are being very, very foolish.


    Thank you!!

    In fact, you direct this words also to the all who believes in benefits
    of "atomicity" (e.g. Doug Lea, ...). My approach is just a bit lighter
    than used in e.g. AtomicInteger ("get-and-set", and the like...). The
    key difference is that my 'source' is not volatile, and I don't care if
    I'm always reusing a new value. I decided to do so, because it WASN'T
    my primary goal -- just a "nice side-effect". If someones goals are
    different, nobody prevents them from being less foolish than me.


    piotr
     
    Piotr Kobzda, Mar 26, 2008
    #19
  20. Lew Guest

    Piotr Kobzda wrote:
    >>>>> while (source.length() < length)
    >>>>> this.source = source += source;


    Lew wrote:
    >>>> Why are you assigning the string twice each iteration, once to the
    >>>> local variable and once to the instance variable?


    Piotr Kobzda wrote:
    >>> It's to let access as soon as possible the newly created string by
    >>> the other concurrently running threads.
    >>>
    >>> Yes, I know, that the Java memory model do not guarantee this (field


    Lew wrote:
    >> In fact, it pretty much guarantees that for some runs, the threads
    >> will *not* see the changes made by each other.


    Piotr Kobzda wrote:
    > So what? My primary goal was logic validity. Even if some threads
    > won't see the changes, they will build their own strings, and the logic
    > correctness is preserved.


    Oh, a missing detail. You didn't mention that before.

    It's a very funky idiom, and a micro-optimization that will make no noticeable
    difference to performance, but it's at least set up so that you won't get
    incorrect results, from what you say. Also, more important, you've at least
    thought about the consequences.

    Still, it's a questionable gain, if any, in performance for an idiom that begs
    for maintenance headaches. You do realize that current JVMs have optimized
    away synchronization overhead from many common scenarios, right?

    --
    Lew
     
    Lew, Mar 26, 2008
    #20
    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. Replies:
    4
    Views:
    285
  2. deepak
    Replies:
    1
    Views:
    293
    Daniel Pitts
    Jan 31, 2007
  3. joshc
    Replies:
    14
    Views:
    796
    Keith Thompson
    Jan 14, 2005
  4. Siduction
    Replies:
    0
    Views:
    298
    Siduction
    Mar 20, 2009
  5. kiran
    Replies:
    12
    Views:
    1,162
    Scott Sauyet
    Dec 7, 2011
Loading...

Share This Page