Fastest way to iterate over all the chars in a String
JavaStringPerformanceCharIterationJava Problem Overview
In Java, what would the fastest way to iterate over all the chars in a String, this:
String str = "a really, really long string";
for (int i = 0, n = str.length(); i < n; i++) {
char c = str.charAt(i);
}
Or this:
char[] chars = str.toCharArray();
for (int i = 0, n = chars.length; i < n; i++) {
char c = chars[i];
}
EDIT :
What I'd like to know is if the cost of repeatedly calling the charAt method during a long iteration ends up being either less than or greater than the cost of performing a single call to toCharArray at the beginning and then directly accessing the array during the iteration.
It'd be great if someone could provide a robust benchmark for different string lengths, having in mind JIT warm-up time, JVM start-up time, etc. and not just the difference between two calls to System.currentTimeMillis().
Java Solutions
Solution 1 - Java
FIRST UPDATE: Before you try this ever in a production environment (not advised), read this first: http://www.javaspecialists.eu/archive/Issue237.html Starting from Java 9, the solution as described won't work anymore, because now Java will store strings as byte[] by default.
SECOND UPDATE: As of 2016-10-25, on my AMDx64 8core and source 1.8, there is no difference between using 'charAt' and field access. It appears that the jvm is sufficiently optimized to inline and streamline any 'string.charAt(n)' calls.
THIRD UPDATE: As of 2020-09-07, on my Ryzen 1950-X 16 core and source 1.14, 'charAt1' is 9 times slower than field access and 'charAt2' is 4 times slower than field access. Field access is back as the clear winner. Note than the program will need to use byte[] access for Java 9+ version jvms.
It all depends on the length of the String being inspected. If, as the question says, it is for long strings, the fastest way to inspect the string is to use reflection to access the backing char[] of the string.
A fully randomized benchmark with JDK 8 (win32 and win64) on an 64 AMD Phenom II 4 core 955 @ 3.2 GHZ (in both client mode and server mode) with 9 different techniques (see below!) shows that using String.charAt(n) is the fastest for small strings and that using reflection to access the String backing array is almost twice as fast for large strings.
THE EXPERIMENT
-
9 different optimization techniques are tried.
-
All string contents are randomized
-
The test are done for string sizes in multiples of two starting with 0,1,2,4,8,16 etc.
-
The tests are done 1,000 times per string size
-
The tests are shuffled into random order each time. In other words, the tests are done in random order every time they are done, over 1000 times over.
-
The entire test suite is done forwards, and backwards, to show the effect of JVM warmup on optimization and times.
-
The entire suite is done twice, once in
-clientmode and the other in-servermode.
CONCLUSIONS
-client mode (32 bit)
For strings 1 to 256 characters in length, calling string.charAt(i) wins with an average processing of 13.4 million to 588 million characters per second.
Also, it is overall 5.5% faster (client) and 13.9% (server) like this:
for (int i = 0; i < data.length(); i++) {
if (data.charAt(i) <= ' ') {
doThrow();
}
}
than like this with a local final length variable:
final int len = data.length();
for (int i = 0; i < len; i++) {
if (data.charAt(i) <= ' ') {
doThrow();
}
}
For long strings, 512 to 256K characters length, using reflection to access the String's backing array is fastest. This technique is almost twice as fast as String.charAt(i) (178% faster). The average speed over this range was 1.111 billion characters per second.
The Field must be obtained ahead of time and then it can be re-used in the library on different strings. Interestingly, unlike the code above, with Field access, it is 9% faster to have a local final length variable than to use 'chars.length' in the loop check. Here is how Field access can be setup as fastest:
final Field field = String.class.getDeclaredField("value");
field.setAccessible(true);
try {
final char[] chars = (char[]) field.get(data);
final int len = chars.length;
for (int i = 0; i < len; i++) {
if (chars[i] <= ' ') {
doThrow();
}
}
return len;
} catch (Exception ex) {
throw new RuntimeException(ex);
}
Special comments on -server mode
Field access starting winning after 32 character length strings in server mode on a 64 bit Java machine on my AMD 64 machine. That was not seen until 512 characters length in client mode.
Also worth noting I think, when I was running JDK 8 (32 bit build) in server mode, the overall performance was 7% slower for both large and small strings. This was with build 121 Dec 2013 of JDK 8 early release. So, for now, it seems that 32 bit server mode is slower than 32 bit client mode.
That being said ... it seems the only server mode that is worth invoking is on a 64 bit machine. Otherwise it actually hampers performance.
For 32 bit build running in -server mode on an AMD64, I can say this:
- String.charAt(i) is the clear winner overall. Although between sizes 8 to 512 characters there were winners among 'new' 'reuse' and 'field'.
- String.charAt(i) is 45% faster in client mode
- Field access is twice as fast for large Strings in client mode.
Also worth saying, String.chars() (Stream and the parallel version) are a bust. Way slower than any other way. The Streams API is a rather slow way to perform general string operations.
Wish List
Java String could have predicate accepting optimized methods such as contains(predicate), forEach(consumer), forEachWithIndex(consumer). Thus, without the need for the user to know the length or repeat calls to String methods, these could help parsing libraries beep-beep beep speedup.
Keep dreaming :)
Happy Strings!
~SH
The test used the following 9 methods of testing the string for the presence of whitespace:
"charAt1" -- CHECK THE STRING CONTENTS THE USUAL WAY:
int charAtMethod1(final String data) {
final int len = data.length();
for (int i = 0; i < len; i++) {
if (data.charAt(i) <= ' ') {
doThrow();
}
}
return len;
}
"charAt2" -- SAME AS ABOVE BUT USE String.length() INSTEAD OF MAKING A FINAL LOCAL int FOR THE LENGTh
int charAtMethod2(final String data) {
for (int i = 0; i < data.length(); i++) {
if (data.charAt(i) <= ' ') {
doThrow();
}
}
return data.length();
}
"stream" -- USE THE NEW JAVA-8 String's IntStream AND PASS IT A PREDICATE TO DO THE CHECKING
int streamMethod(final String data, final IntPredicate predicate) {
if (data.chars().anyMatch(predicate)) {
doThrow();
}
return data.length();
}
"streamPara" -- SAME AS ABOVE, BUT OH-LA-LA - GO PARALLEL!!!
// avoid this at all costs
int streamParallelMethod(final String data, IntPredicate predicate) {
if (data.chars().parallel().anyMatch(predicate)) {
doThrow();
}
return data.length();
}
"reuse" -- REFILL A REUSABLE char[] WITH THE STRINGS CONTENTS
int reuseBuffMethod(final char[] reusable, final String data) {
final int len = data.length();
data.getChars(0, len, reusable, 0);
for (int i = 0; i < len; i++) {
if (reusable[i] <= ' ') {
doThrow();
}
}
return len;
}
"new1" -- OBTAIN A NEW COPY OF THE char[] FROM THE STRING
int newMethod1(final String data) {
final int len = data.length();
final char[] copy = data.toCharArray();
for (int i = 0; i < len; i++) {
if (copy[i] <= ' ') {
doThrow();
}
}
return len;
}
"new2" -- SAME AS ABOVE, BUT USE "FOR-EACH"
int newMethod2(final String data) {
for (final char c : data.toCharArray()) {
if (c <= ' ') {
doThrow();
}
}
return data.length();
}
"field1" -- FANCY!! OBTAIN FIELD FOR ACCESS TO THE STRING'S INTERNAL char[]
int fieldMethod1(final Field field, final String data) {
try {
final char[] chars = (char[]) field.get(data);
final int len = chars.length;
for (int i = 0; i < len; i++) {
if (chars[i] <= ' ') {
doThrow();
}
}
return len;
} catch (Exception ex) {
throw new RuntimeException(ex);
}
}
"field2" -- SAME AS ABOVE, BUT USE "FOR-EACH"
int fieldMethod2(final Field field, final String data) {
final char[] chars;
try {
chars = (char[]) field.get(data);
} catch (Exception ex) {
throw new RuntimeException(ex);
}
for (final char c : chars) {
if (c <= ' ') {
doThrow();
}
}
return chars.length;
}
COMPOSITE RESULTS FOR CLIENT -client MODE (forwards and backwards tests combined)
Note: that the -client mode with Java 32 bit and -server mode with Java 64 bit are the same as below on my AMD64 machine.
Size WINNER charAt1 charAt2 stream streamPar reuse new1 new2 field1 field2
1 charAt 77.0 72.0 462.0 584.0 127.5 89.5 86.0 159.5 165.0
2 charAt 38.0 36.5 284.0 32712.5 57.5 48.3 50.3 89.0 91.5
4 charAt 19.5 18.5 458.6 3169.0 33.0 26.8 27.5 54.1 52.6
8 charAt 9.8 9.9 100.5 1370.9 17.3 14.4 15.0 26.9 26.4
16 charAt 6.1 6.5 73.4 857.0 8.4 8.2 8.3 13.6 13.5
32 charAt 3.9 3.7 54.8 428.9 5.0 4.9 4.7 7.0 7.2
64 charAt 2.7 2.6 48.2 232.9 3.0 3.2 3.3 3.9 4.0
128 charAt 2.1 1.9 43.7 138.8 2.1 2.6 2.6 2.4 2.6
256 charAt 1.9 1.6 42.4 90.6 1.7 2.1 2.1 1.7 1.8
512 field1 1.7 1.4 40.6 60.5 1.4 1.9 1.9 1.3 1.4
1,024 field1 1.6 1.4 40.0 45.6 1.2 1.9 2.1 1.0 1.2
2,048 field1 1.6 1.3 40.0 36.2 1.2 1.8 1.7 0.9 1.1
4,096 field1 1.6 1.3 39.7 32.6 1.2 1.8 1.7 0.9 1.0
8,192 field1 1.6 1.3 39.6 30.5 1.2 1.8 1.7 0.9 1.0
16,384 field1 1.6 1.3 39.8 28.4 1.2 1.8 1.7 0.8 1.0
32,768 field1 1.6 1.3 40.0 26.7 1.3 1.8 1.7 0.8 1.0
65,536 field1 1.6 1.3 39.8 26.3 1.3 1.8 1.7 0.8 1.0
131,072 field1 1.6 1.3 40.1 25.4 1.4 1.9 1.8 0.8 1.0
262,144 field1 1.6 1.3 39.6 25.2 1.5 1.9 1.9 0.8 1.0
COMPOSITE RESULTS FOR SERVER -server MODE (forwards and backwards tests combined)
Note: this is the test for Java 32 bit running in server mode on an AMD64. The server mode for Java 64 bit was the same as Java 32 bit in client mode except that Field access starting winning after 32 characters size.
Size WINNER charAt1 charAt2 stream streamPar reuse new1 new2 field1 field2
1 charAt 74.5 95.5 524.5 783.0 90.5 102.5 90.5 135.0 151.5
2 charAt 48.5 53.0 305.0 30851.3 59.3 57.5 52.0 88.5 91.8
4 charAt 28.8 32.1 132.8 2465.1 37.6 33.9 32.3 49.0 47.0
8 new2 18.0 18.6 63.4 1541.3 18.5 17.9 17.6 25.4 25.8
16 new2 14.0 14.7 129.4 1034.7 12.5 16.2 12.0 16.0 16.6
32 new2 7.8 9.1 19.3 431.5 8.1 7.0 6.7 7.9 8.7
64 reuse 6.1 7.5 11.7 204.7 3.5 3.9 4.3 4.2 4.1
128 reuse 6.8 6.8 9.0 101.0 2.6 3.0 3.0 2.6 2.7
256 field2 6.2 6.5 6.9 57.2 2.4 2.7 2.9 2.3 2.3
512 reuse 4.3 4.9 5.8 28.2 2.0 2.6 2.6 2.1 2.1
1,024 charAt 2.0 1.8 5.3 17.6 2.1 2.5 3.5 2.0 2.0
2,048 charAt 1.9 1.7 5.2 11.9 2.2 3.0 2.6 2.0 2.0
4,096 charAt 1.9 1.7 5.1 8.7 2.1 2.6 2.6 1.9 1.9
8,192 charAt 1.9 1.7 5.1 7.6 2.2 2.5 2.6 1.9 1.9
16,384 charAt 1.9 1.7 5.1 6.9 2.2 2.5 2.5 1.9 1.9
32,768 charAt 1.9 1.7 5.1 6.1 2.2 2.5 2.5 1.9 1.9
65,536 charAt 1.9 1.7 5.1 5.5 2.2 2.4 2.4 1.9 1.9
131,072 charAt 1.9 1.7 5.1 5.4 2.3 2.5 2.5 1.9 1.9
262,144 charAt 1.9 1.7 5.1 5.1 2.3 2.5 2.5 1.9 1.9
FULL RUNNABLE PROGRAM CODE
(to test on Java 7 and earlier, remove the two streams tests)
import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.function.IntPredicate;
/**
* @author Saint Hill <http://stackoverflow.com/users/1584255/saint-hill>
*/
public final class TestStrings {
// we will not test strings longer than 512KM
final int MAX_STRING_SIZE = 1024 * 256;
// for each string size, we will do all the tests
// this many times
final int TRIES_PER_STRING_SIZE = 1000;
public static void main(String[] args) throws Exception {
new TestStrings().run();
}
void run() throws Exception {
// double the length of the data until it reaches MAX chars long
// 0,1,2,4,8,16,32,64,128,256 ...
final List<Integer> sizes = new ArrayList<>();
for (int n = 0; n <= MAX_STRING_SIZE; n = (n == 0 ? 1 : n * 2)) {
sizes.add(n);
}
// CREATE RANDOM (FOR SHUFFLING ORDER OF TESTS)
final Random random = new Random();
System.out.println("Rate in nanoseconds per character inspected.");
System.out.printf("==== FORWARDS (tries per size: %s) ==== \n", TRIES_PER_STRING_SIZE);
printHeadings(TRIES_PER_STRING_SIZE, random);
for (int size : sizes) {
reportResults(size, test(size, TRIES_PER_STRING_SIZE, random));
}
// reverse order or string sizes
Collections.reverse(sizes);
System.out.println("");
System.out.println("Rate in nanoseconds per character inspected.");
System.out.printf("==== BACKWARDS (tries per size: %s) ==== \n", TRIES_PER_STRING_SIZE);
printHeadings(TRIES_PER_STRING_SIZE, random);
for (int size : sizes) {
reportResults(size, test(size, TRIES_PER_STRING_SIZE, random));
}
}
///
///
/// METHODS OF CHECKING THE CONTENTS
/// OF A STRING. ALWAYS CHECKING FOR
/// WHITESPACE (CHAR <=' ')
///
///
// CHECK THE STRING CONTENTS
int charAtMethod1(final String data) {
final int len = data.length();
for (int i = 0; i < len; i++) {
if (data.charAt(i) <= ' ') {
doThrow();
}
}
return len;
}
// SAME AS ABOVE BUT USE String.length()
// instead of making a new final local int
int charAtMethod2(final String data) {
for (int i = 0; i < data.length(); i++) {
if (data.charAt(i) <= ' ') {
doThrow();
}
}
return data.length();
}
// USE new Java-8 String's IntStream
// pass it a PREDICATE to do the checking
int streamMethod(final String data, final IntPredicate predicate) {
if (data.chars().anyMatch(predicate)) {
doThrow();
}
return data.length();
}
// OH LA LA - GO PARALLEL!!!
int streamParallelMethod(final String data, IntPredicate predicate) {
if (data.chars().parallel().anyMatch(predicate)) {
doThrow();
}
return data.length();
}
// Re-fill a resuable char[] with the contents
// of the String's char[]
int reuseBuffMethod(final char[] reusable, final String data) {
final int len = data.length();
data.getChars(0, len, reusable, 0);
for (int i = 0; i < len; i++) {
if (reusable[i] <= ' ') {
doThrow();
}
}
return len;
}
// Obtain a new copy of char[] from String
int newMethod1(final String data) {
final int len = data.length();
final char[] copy = data.toCharArray();
for (int i = 0; i < len; i++) {
if (copy[i] <= ' ') {
doThrow();
}
}
return len;
}
// Obtain a new copy of char[] from String
// but use FOR-EACH
int newMethod2(final String data) {
for (final char c : data.toCharArray()) {
if (c <= ' ') {
doThrow();
}
}
return data.length();
}
// FANCY!
// OBTAIN FIELD FOR ACCESS TO THE STRING'S
// INTERNAL CHAR[]
int fieldMethod1(final Field field, final String data) {
try {
final char[] chars = (char[]) field.get(data);
final int len = chars.length;
for (int i = 0; i < len; i++) {
if (chars[i] <= ' ') {
doThrow();
}
}
return len;
} catch (Exception ex) {
throw new RuntimeException(ex);
}
}
// same as above but use FOR-EACH
int fieldMethod2(final Field field, final String data) {
final char[] chars;
try {
chars = (char[]) field.get(data);
} catch (Exception ex) {
throw new RuntimeException(ex);
}
for (final char c : chars) {
if (c <= ' ') {
doThrow();
}
}
return chars.length;
}
/**
*
* Make a list of tests. We will shuffle a copy of this list repeatedly
* while we repeat this test.
*
* @param data
* @return
*/
List<Jobber> makeTests(String data) throws Exception {
// make a list of tests
final List<Jobber> tests = new ArrayList<Jobber>();
tests.add(new Jobber("charAt1") {
int check() {
return charAtMethod1(data);
}
});
tests.add(new Jobber("charAt2") {
int check() {
return charAtMethod2(data);
}
});
tests.add(new Jobber("stream") {
final IntPredicate predicate = new IntPredicate() {
public boolean test(int value) {
return value <= ' ';
}
};
int check() {
return streamMethod(data, predicate);
}
});
tests.add(new Jobber("streamPar") {
final IntPredicate predicate = new IntPredicate() {
public boolean test(int value) {
return value <= ' ';
}
};
int check() {
return streamParallelMethod(data, predicate);
}
});
// Reusable char[] method
tests.add(new Jobber("reuse") {
final char[] cbuff = new char[MAX_STRING_SIZE];
int check() {
return reuseBuffMethod(cbuff, data);
}
});
// New char[] from String
tests.add(new Jobber("new1") {
int check() {
return newMethod1(data);
}
});
// New char[] from String
tests.add(new Jobber("new2") {
int check() {
return newMethod2(data);
}
});
// Use reflection for field access
tests.add(new Jobber("field1") {
final Field field;
{
field = String.class.getDeclaredField("value");
field.setAccessible(true);
}
int check() {
return fieldMethod1(field, data);
}
});
// Use reflection for field access
tests.add(new Jobber("field2") {
final Field field;
{
field = String.class.getDeclaredField("value");
field.setAccessible(true);
}
int check() {
return fieldMethod2(field, data);
}
});
return tests;
}
/**
* We use this class to keep track of test results
*/
abstract class Jobber {
final String name;
long nanos;
long chars;
long runs;
Jobber(String name) {
this.name = name;
}
abstract int check();
final double nanosPerChar() {
double charsPerRun = chars / runs;
long nanosPerRun = nanos / runs;
return charsPerRun == 0 ? nanosPerRun : nanosPerRun / charsPerRun;
}
final void run() {
runs++;
long time = System.nanoTime();
chars += check();
nanos += System.nanoTime() - time;
}
}
// MAKE A TEST STRING OF RANDOM CHARACTERS A-Z
private String makeTestString(int testSize, char start, char end) {
Random r = new Random();
char[] data = new char[testSize];
for (int i = 0; i < data.length; i++) {
data[i] = (char) (start + r.nextInt(end));
}
return new String(data);
}
// WE DO THIS IF WE FIND AN ILLEGAL CHARACTER IN THE STRING
public void doThrow() {
throw new RuntimeException("Bzzzt -- Illegal Character!!");
}
/**
* 1. get random string of correct length 2. get tests (List<Jobber>) 3.
* perform tests repeatedly, shuffling each time
*/
List<Jobber> test(int size, int tries, Random random) throws Exception {
String data = makeTestString(size, 'A', 'Z');
List<Jobber> tests = makeTests(data);
List<Jobber> copy = new ArrayList<>(tests);
while (tries-- > 0) {
Collections.shuffle(copy, random);
for (Jobber ti : copy) {
ti.run();
}
}
// check to make sure all char counts the same
long runs = tests.get(0).runs;
long count = tests.get(0).chars;
for (Jobber ti : tests) {
if (ti.runs != runs && ti.chars != count) {
throw new Exception("Char counts should match if all correct algorithms");
}
}
return tests;
}
private void printHeadings(final int TRIES_PER_STRING_SIZE, final Random random) throws Exception {
System.out.print(" Size");
for (Jobber ti : test(0, TRIES_PER_STRING_SIZE, random)) {
System.out.printf("%9s", ti.name);
}
System.out.println("");
}
private void reportResults(int size, List<Jobber> tests) {
System.out.printf("%6d", size);
for (Jobber ti : tests) {
System.out.printf("%,9.2f", ti.nanosPerChar());
}
System.out.println("");
}
}
Solution 2 - Java
This is just micro-optimisation that you shouldn't worry about.
char[] chars = str.toCharArray();
returns you a copy of str character arrays (in JDK, it returns a copy of characters by calling System.arrayCopy).
Other than that, str.charAt() only checks if the index is indeed in bounds and returns a character within the array index.
The first one doesn't create additional memory in JVM.
Solution 3 - Java
Just for curiosity and to compare with Saint Hill's answer.
If you need to process heavy data you should not use JVM in client mode. Client mode is not made for optimizations.
Let's compare results of @Saint Hill benchmarks using a JVM in Client mode and Server mode.
Core2Quad Q6600 G0 @ 2.4GHz
JavaSE 1.7.0_40
See also: https://stackoverflow.com/questions/198577/real-differences-between-java-server-and-java-client
CLIENT MODE:
len = 2: 111k charAt(i), 105k cbuff[i], 62k new[i], 17k field access. (chars/ms)
len = 4: 285k charAt(i), 166k cbuff[i], 114k new[i], 43k field access. (chars/ms)
len = 6: 315k charAt(i), 230k cbuff[i], 162k new[i], 69k field access. (chars/ms)
len = 8: 333k charAt(i), 275k cbuff[i], 181k new[i], 85k field access. (chars/ms)
len = 12: 342k charAt(i), 342k cbuff[i], 222k new[i], 117k field access. (chars/ms)
len = 16: 363k charAt(i), 347k cbuff[i], 275k new[i], 152k field access. (chars/ms)
len = 20: 363k charAt(i), 392k cbuff[i], 289k new[i], 180k field access. (chars/ms)
len = 24: 375k charAt(i), 428k cbuff[i], 311k new[i], 205k field access. (chars/ms)
len = 28: 378k charAt(i), 474k cbuff[i], 341k new[i], 233k field access. (chars/ms)
len = 32: 376k charAt(i), 492k cbuff[i], 340k new[i], 251k field access. (chars/ms)
len = 64: 374k charAt(i), 551k cbuff[i], 374k new[i], 367k field access. (chars/ms)
len = 128: 385k charAt(i), 624k cbuff[i], 415k new[i], 509k field access. (chars/ms)
len = 256: 390k charAt(i), 675k cbuff[i], 436k new[i], 619k field access. (chars/ms)
len = 512: 394k charAt(i), 703k cbuff[i], 439k new[i], 695k field access. (chars/ms)
len = 1024: 395k charAt(i), 718k cbuff[i], 462k new[i], 742k field access. (chars/ms)
len = 2048: 396k charAt(i), 725k cbuff[i], 471k new[i], 767k field access. (chars/ms)
len = 4096: 396k charAt(i), 727k cbuff[i], 459k new[i], 780k field access. (chars/ms)
len = 8192: 397k charAt(i), 712k cbuff[i], 446k new[i], 772k field access. (chars/ms)
SERVER MODE:
len = 2: 86k charAt(i), 41k cbuff[i], 46k new[i], 80k field access. (chars/ms)
len = 4: 571k charAt(i), 250k cbuff[i], 97k new[i], 222k field access. (chars/ms)
len = 6: 666k charAt(i), 333k cbuff[i], 125k new[i], 315k field access. (chars/ms)
len = 8: 800k charAt(i), 400k cbuff[i], 181k new[i], 380k field access. (chars/ms)
len = 12: 800k charAt(i), 521k cbuff[i], 260k new[i], 545k field access. (chars/ms)
len = 16: 800k charAt(i), 592k cbuff[i], 296k new[i], 640k field access. (chars/ms)
len = 20: 800k charAt(i), 666k cbuff[i], 408k new[i], 800k field access. (chars/ms)
len = 24: 800k charAt(i), 705k cbuff[i], 452k new[i], 800k field access. (chars/ms)
len = 28: 777k charAt(i), 736k cbuff[i], 368k new[i], 933k field access. (chars/ms)
len = 32: 800k charAt(i), 780k cbuff[i], 571k new[i], 969k field access. (chars/ms)
len = 64: 800k charAt(i), 901k cbuff[i], 800k new[i], 1306k field access. (chars/ms)
len = 128: 1084k charAt(i), 888k cbuff[i], 633k new[i], 1620k field access. (chars/ms)
len = 256: 1122k charAt(i), 966k cbuff[i], 729k new[i], 1790k field access. (chars/ms)
len = 512: 1163k charAt(i), 1007k cbuff[i], 676k new[i], 1910k field access. (chars/ms)
len = 1024: 1179k charAt(i), 1027k cbuff[i], 698k new[i], 1954k field access. (chars/ms)
len = 2048: 1184k charAt(i), 1043k cbuff[i], 732k new[i], 2007k field access. (chars/ms)
len = 4096: 1188k charAt(i), 1049k cbuff[i], 742k new[i], 2031k field access. (chars/ms)
len = 8192: 1157k charAt(i), 1032k cbuff[i], 723k new[i], 2048k field access. (chars/ms)
CONCLUSION:
As you can see, server mode is much faster.
Solution 4 - Java
The first one using str.charAt should be faster.
If you dig inside the source code of String class, we can see that charAt is implemented as follows:
public char charAt(int index) {
if ((index < 0) || (index >= count)) {
throw new StringIndexOutOfBoundsException(index);
}
return value[index + offset];
}
Here, all it does is index an array and return the value.
Now, if we see the implementation of toCharArray, we will find the below:
public char[] toCharArray() {
char result[] = new char[count];
getChars(0, count, result, 0);
return result;
}
public void getChars(int srcBegin, int srcEnd, char dst[], int dstBegin) {
if (srcBegin < 0) {
throw new StringIndexOutOfBoundsException(srcBegin);
}
if (srcEnd > count) {
throw new StringIndexOutOfBoundsException(srcEnd);
}
if (srcBegin > srcEnd) {
throw new StringIndexOutOfBoundsException(srcEnd - srcBegin);
}
System.arraycopy(value, offset + srcBegin, dst, dstBegin,
srcEnd - srcBegin);
}
As you see, it is doing a System.arraycopy which is definitely going to be a tad slower than not doing it.
Solution 5 - Java
String.toCharArray() creates new char array, means allocation of memory of string length, then copies original char array of string using System.arraycopy() and then returns this copy to caller.
String.charAt() returns character at position i from original copy, that's why String.charAt() will be faster than String.toCharArray().
Although, String.toCharArray() returns copy and not char from original String array, where String.charAt() returns character from original char array.
Code below returns value at the specified index of this string.
public char charAt(int index) {
if ((index < 0) || (index >= value.length)) {
throw new StringIndexOutOfBoundsException(index);
}
return value[index];
}
code below returns a newly allocated character array whose length is the length of this string
public char[] toCharArray() {
// Cannot use Arrays.copyOf because of class initialization order issues
char result[] = new char[value.length];
System.arraycopy(value, 0, result, 0, value.length);
return result;
}
Solution 6 - Java
Despite @Saint Hill's answer if you consider the time complexity of str.toCharArray(),
the first one is faster even for very large strings. You can run the code below to see it for yourself.
char [] ch = new char[1_000_000_00];
String str = new String(ch); // to create a large string
// ---> from here
long currentTime = System.nanoTime();
for (int i = 0, n = str.length(); i < n; i++) {
char c = str.charAt(i);
}
// ---> to here
System.out.println("str.charAt(i):"+(System.nanoTime()-currentTime)/1000000.0 +" (ms)");
/**
* ch = str.toCharArray() itself takes lots of time
*/
// ---> from here
currentTime = System.nanoTime();
ch = str.toCharArray();
for (int i = 0, n = str.length(); i < n; i++) {
char c = ch[i];
}
// ---> to here
System.out.println("ch = str.toCharArray() + c = ch[i] :"+(System.nanoTime()-currentTime)/1000000.0 +" (ms)");
output:
str.charAt(i):5.492102 (ms)
ch = str.toCharArray() + c = ch[i] :79.400064 (ms)
Solution 7 - Java
Looks like niether is faster or slower
public static void main(String arguments[]) {
//Build a long string
StringBuilder sb = new StringBuilder();
for(int j = 0; j < 10000; j++) {
sb.append("a really, really long string");
}
String str = sb.toString();
for (int testscount = 0; testscount < 10; testscount ++) {
//Test 1
long start = System.currentTimeMillis();
for(int c = 0; c < 10000000; c++) {
for (int i = 0, n = str.length(); i < n; i++) {
char chr = str.charAt(i);
doSomethingWithChar(chr);//To trick JIT optimistaion
}
}
System.out.println("1: " + (System.currentTimeMillis() - start));
//Test 2
start = System.currentTimeMillis();
char[] chars = str.toCharArray();
for(int c = 0; c < 10000000; c++) {
for (int i = 0, n = chars.length; i < n; i++) {
char chr = chars[i];
doSomethingWithChar(chr);//To trick JIT optimistaion
}
}
System.out.println("2: " + (System.currentTimeMillis() - start));
System.out.println();
}
}
public static void doSomethingWithChar(char chr) {
int newInt = chr << 2;
}
For long strings I'll chose the first one. Why copy around long strings? Documentations says: > public char[] toCharArray() > Converts this string to a new character array. > > Returns: > a newly allocated character array whose length is the length of this string and whose contents are initialized to contain the character sequence represented by this string.
//Edit 1
I've changed the test to trick JIT optimisation.
//Edit 2
Repeat test 10 times to let JVM warm up.
//Edit 3
Conclusions:
First of all str.toCharArray(); copies entire string in memory. It can be memory consuming for long strings. Method String.charAt( ) looks up char in char array inside String class checking index before.
It looks like for short enough Strings first method (i.e. chatAt method) is a bit slower due to this index check. But if the String is long enough, copying whole char array gets slower, and the first method is faster. The longer the string is, the slower toCharArray performs. Try to change limit in for(int j = 0; j < 10000; j++) loop to see it.
If we let JVM warm up code runs faster, but proportions are the same.
After all it's just micro-optimisation.
Solution 8 - Java
The second one causes a new char array to be created, and all chars from the String to be copied to this new char array, so I would guess that the first one is faster (and less memory-hungry).