ArrayList vs String in Java

Question

I am implementing the LZW algorithm. I have implemented it for strings and text files successfully and am currently modifying my code to work with binary files, such as images or executables (since I cannot read these files as strings).

I have replaced the String type in my code with the ArrayList<Byte> type. My code now compresses and decompresses binary files correctly, however it is at least 10x slower! This is unacceptable in a compression application where speed is a critical element.

Have I made the correct substitution of ArrayList<Byte> for String. Is there a faster alternative with similar functionality? Note that the LZW algorithm requires array resizing hence standard arrays[] are not suitable.

Regards.

you should show your code, there may be other obvious reasons for the performance hit. — T McKeown, Jan 21 '14 at 00:22

score 6 · Answer 1 · answered Jan 21 '14 at 00:24

6

Using a List<Byte> will box every byte into a separate object instance.
In bulk, that is one of the worst possible things you can do for performance.

By contrast, an array or string can occupy a solid block of memory.

Instead, you should use ByteArrayOutputStream, or use byte[] directly and resize as needed (you can make a wrapper class for that)

answered Jan 21 '14 at 00:24

SLaks

868,454
176
1,908
1,964

2

+1 The "solid block of memory" is probably key here. A computationally intensive operation like compression is likely going to benefit a lot from the increased memory locality. – yshavit Jan 21 '14 at 00:26

score 1 · Answer 2 · answered Jan 21 '14 at 00:25

You are boxing bytes within an ArrayList, which uses much more memory than simple Strings. What this means is each byte is wrapped in a whole object, and referred to by a reference. Note that such a reference is itself 4 to 8 times larger than the original byte!

You would be much better off using primitive byte [] arrays, or perhaps a primitive collections library (which properly abstracts primitive arrays as collections) such as this or this.

score 0 · Answer 3 · edited May 23 '17 at 10:25

0

You need to locate the section of the code that is causing the slow down. There is not enough information in the question to gain any useful answers.

You should use a profiler. See this thread: Which Java Profiling tool do you use and which tool you think is the best?

edited May 23 '17 at 10:25

Community

1
1

answered Jan 21 '14 at 00:25

da_steve101

283
4
16

score 0 · Answer 4 · edited May 23 '17 at 10:31

0

ArrayList implements an array so it is not ideal for lots of resizing. LinkedList should give better performance if resizing is creating the bottleneck.

https://stackoverflow.com/a/322742/1487030

edited May 23 '17 at 10:31

Community

1
1

answered Jan 21 '14 at 00:26

matt

350
1
6

1

If memory locality is the culprit (as I suspect), a `LinkedList` would perform even worse. – yshavit Jan 21 '14 at 00:28
When I mentioned resizing in the question. I meant the equivalent of String = String + char; so ArrayList.add(byte); – Danny Rancher Jan 21 '14 at 00:28

ArrayList vs String in Java

4 Answers4

Linked