Custom array wrapper class casting safety/efficiency

Question

I am writing a java application that requires a generic list. This list needs to be capable of being resized dynamically and fairly often, the obvious answer for this would be a generic Linkedlist. Unfortunately, it also needs to get/set values just as frequently as it adds/removes them via calling an index. This would be solved rather nicely by an Arraylist. Since both of these options weren't quite what I was looking for I created my own generic array wrapper class. I have known for quite some time that it is illegal in java to create a generic array, and I have read that typically instead of using generics to define the type of your array, one would just create an object[] array and then cast each element individually to the proper type. This is similar to what Arraylist already does; however, I have read that casting is a very expensive operation in java. So, to get around the necessity of casting, my custom wrapper class looks something like this.

public abstract class CustomArrayWrapper<E extends Object>{
    private E[] content;

    public abstract E[] empty(int n);

    public CustomArrayWrapper(){
        this.content = empty(0);
    }

    public CustomArrayWrapper(int n){
        this.content = empty(n);
    }

    public CustomArrayWrapper(E[] content){
        this.content = content;
    }

    public E[] content(){
        return content;
    }
}

This is just the bare bones of the class, but the main idea, is that each specific use of the array wrapper extends the empty(int n) method, returning an array of size n that is of type E hopefully avoiding all of that expensive casting. An example is as follows using String as the type.

public class StringArrayWrapper extends CustomArrayWrapper<String>{

    public StringArrayWrapper(){
        super();
    }

    public StringArrayWrapper(int n){
        super(n);
    }

    public StringArrayWrapper(String[] content){
        super(content);
    }

    public String[] empty(int n){
        return new String[n];
    }
}

I know that this implementation works, what I don't know is

Is this safe to implement?
I know casting is a little finicky as there is a lot of implicit casting built into java, is this actually a way to get around all of the casting that an Arraylist already performs?
Is it more/less efficient than casting every element to the proper type as in an ArrayList?

"I have read that casting is a very expensive operation in java" - is it really? Do you have numbers to back that up? — sisyphus, Dec 29 '16 at 23:22
@sisyphus There is *some* overhead, see http://stackoverflow.com/questions/2170872/does-java-casting-introduce-overhead-why — lexicore, Dec 29 '16 at 23:23
Not that this fully answers the question, but you can eliminate all method declarations in the subclass save for the concrete implementation of `empty`. What is this being used for that you need access to the array of data instead of using additional getter methods for array indices, and are worried the cost of explicit casting will actually become an issue? — Chris, Dec 29 '16 at 23:25
@lexicore sure, but then everything has *some* overhead. The premise of the question is that `ArrayList` and `LinkedList` can't perform well enough and that casting is 'too expensive'. It's worth investigating those premises before going to the trouble of creating a custom Collection implementation. — sisyphus, Dec 29 '16 at 23:34
@sisyphus *"but then everything has *some* overhead"* - this is definitely not true, not everything has overhead. — lexicore, Dec 29 '16 at 23:41
@sisyphus You're right that it is reasonable to run benchmarks before writing a custom collection, but there definitely are cases where a custom array/linked list combo will make sense and is worth implementing. — lexicore, Dec 29 '16 at 23:42

SkyTyper · Answer 1 · 2016-12-29T23:48:20.913

I recommend you not to put effort and time trying to create your custom collection type, since standard Java API already has plenty of them. You'll win time and you'll be sure it is safe and fully functional.
For example, if you do need to resize quite often and also get and set items quite often, I would choose some of these:

1- If you need more direct access than resizing: Definitely go for an ArrayList.
2- If you need more rezising than direct access: You can use a LinkedList.

I would try yo use a HashMap, since it is a collection that tries to optimise both direct access and resizing, so probably is the best choice for you. The only difference is that you'll have to use a key instead of an index to acces the values inside the collection, but you can still use an Integer key in the same way you an int index in an array. A good thing is you can use any kind of object as the key aswell.

Furthermore, you can use a LinkedHashMap, since it will be faster to iterate over the whole collection, if you ever need to do so.

Anyways, I can't assure you these are the best options for you to use, but I can assure you that you'll find a proper (already developed) collection type to use in the Java API.

That's why I recommend you to read the official documentation on collections, you'll get a general idea about them all and be able to choose the most efficient for your particular issue --> https://www.tutorialspoint.com/java/java_collections.htm

+1 for not trying to build a custom collection class. Instead, use existing classes, measure performance. — Jochen Bedersdorfer, Dec 29 '16 at 23:42
A LinkedList is slower than an ArrayList, in all but unrealistic scenarios. The JDK people even consider deprecating it. Resizing an ArrayList is fast. Traversing a linked list is slow. Using a HashMap instead of an ArrayList when what you need is a list (i.e. an ordered, iterable collection) is not a good advice at all. — JB Nizet, Dec 29 '16 at 23:42

score 1 · Accepted Answer · edited May 23 '17 at 12:08

Check unrolled linked list, this might be what you need.

Next, you might want to consider actually implementing a List by extending AbstractList to stay withing the collection framework. An "array wrapper" will end up cumbersome to work with.

Next, casting may have some overhead (see Does Java casting introduce overhead? Why?) but I don't think it's anything worth considering. The downside of your approach is that you'll need to inmplement the empty method on each use. It's a price too high for questionable performance improvements from my point of view.

To answer your questions:

Creating array template method implemented in subclass is OK. What's less safe is that you expose this array in the content method.
I don't think you can get rid of casting. I also don't think casting performance is something to worry about.
Run benchmarks and measure it. I think it will be a little bit more efficient since type checks will not be needed, but this will not be something significant/noticeable.

Custom array wrapper class casting safety/efficiency

2 Answers2