ArrayList<Byte> 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
– T McKeown, Commented Jan 21, 2014 at 0:22

SLaks · Accepted Answer · 2014-01-21 00:24:14Z

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, 2014 at 0:24

SLaks

891k182 gold badges1.9k silver badges2k bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

yshavit Over a year ago

+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.

phs · Accepted Answer · 2014-01-21 00:25:17Z

1

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.

answered Jan 21, 2014 at 0:25

phs

11.1k5 gold badges60 silver badges89 bronze badges

Comments

Community · Accepted Answer · 2017-05-23 10:25:55Z

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, 2017 at 10:25

CommunityBot

11 silver badge

answered Jan 21, 2014 at 0:25

da_steve101

2836 silver badges16 bronze badges

Comments

Community · Accepted Answer · 2017-05-23 10:31:40Z

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, 2017 at 10:31

CommunityBot

11 silver badge

answered Jan 21, 2014 at 0:26

matt

3501 silver badge7 bronze badges

2 Comments

yshavit Over a year ago

If memory locality is the culprit (as I suspect), a LinkedList would perform even worse.

Danny Rancher Over a year ago

When I mentioned resizing in the question. I meant the equivalent of String = String + char; so ArrayList<Byte>.add(byte);

Collectives™ on Stack Overflow

ArrayList<Byte> vs String in Java

4 Answers 4

1 Comment

Comments

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related