how can i optimize the given below code

[programmer.sajjad]

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);

 

[Joshua Cranmer]

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');

 

[Lew]

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?

 

[Eric Sosman]

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

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.

 

[Patricia Shanahan]

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

 

[Piotr Kobzda]

(e-mail address removed) 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]

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

 

[Arne Vajhøj]

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

 

[Eric Sosman]

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.

 

[Stefan Ram]

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.

 

[Lew]

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.

 

[Arne Vajhøj]

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

 

[Stefan Ram]

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 ];

 

[Piotr Kobzda]

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

 

[Lew]

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.

 

[Piotr Kobzda]

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.

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.

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

 

[Lew]

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.

 

[Arne Vajhøj]

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

 

[Piotr Kobzda]

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.

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

 

[Lew]

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?