Java and C++ stack implementations with dramatically different performance

Question

I'm developing a small programming language for use in any project I have where I feel a small scripting language could be used well. I've written two emulators for the language, one in C++ and one in Java. The C++ performs faster except for any recursion in the language, in which it suddenly performs terribly!

Here is the code from my language that I am running which runs in 1.5s on the Java emulator and 4s on the C++ emulator:

dec i = 0;
recurse();
print i;

def recurse:
    if i < 10000000:
        i++;
        recurse();
    return;

This compiles down into the following instructions:

% i = 0; #define the alias i as being variable 0;
# i needs to be initialised;
STOREINT i 0;
CALL @recurse; #call the label recurse, push this line onto the stack;
PRINTINTLN $i;
END; #end of program;

@recurse; #define the function recurse;
# if i is < 10000000 then inc i;
GEQ $i 10000000;
JCMP @return; #jump to the return statement
INC i;
CALL @recurse;
@return; 
RETURN; #return back to the line on the top of the stack;

The C++ implementation differs slightly from the Java implementation in that it uses an array of unions to store each "typeless" object, whereas Java just uses Object. Other than that, the code is almost identical (with C++ not needing to do any casting because from the instructions we can be sure which field in the union we are using, and therefore we access the correct field instead of casting the Object to the correct type in Java. C++ also doesn't need to use & 0xFF in order to fix sign problems with the java byte type, as we can make unsigned chars). The main difference between them seems to be the performance of the call stacks, which are implemented in each case as follows:

Java

public class ArrayStack<T> implements Stack<T>
{
    private static final long serialVersionUID = 1L;
    protected Object[] stack;
    protected int capacity;
    protected int pointer;

    public ArrayStack(int capacity)
    {
        stack = new Object[capacity];
        this.capacity = capacity;
        clear();
    }

    public void push(T value)
    {
        stack[pointer++] = value;
    }

    public T pop()
    {
        return (T) stack[--pointer];
    }

    public T peek()
    {
        return (T) stack[pointer-1];
    }

    public boolean isEmpty()
    {
        return pointer == 0;
    }

    public boolean isFull()
    {
        return pointer == capacity;
    }

    public void clear()
    {
        pointer = 0;
    }

    public int size()
    {
        return pointer;
    }

    public int capacity()
    {
        return capacity;
    }
}

C++

template <class T> class ArrayStack
{
    private:
        T* stack;
        int capacity;
        int pointer;

    public:
        ArrayStack(int capacity)
        {
            this->capacity = capacity;
            stack = new T[capacity];
            clear();
        }

        ~ArrayStack() { delete stack; }
        void push(T value) { stack[pointer++] = value; }
        T pop() { return stack[--pointer]; }
        T peek() const { return stack[pointer-1]; }
        bool isEmpty() const { return pointer == 0; }
        void clear() { pointer = 0; }
        int size() const { return pointer; }
        int getCapacity() { return capacity; }
};

I'll provide the case statements running during this program below if anybody wants to see them, but for now I'll leave them out to keep this post a little shorter!

To my eyes, the C++ looks like it should be either faster than or equal to the Java one, as even if new was the slow part of the C++ code, that isn't taken into account in the timing of the program execution, which starts timing as soon as the first instruction is executed. Could it be that I'm storing the stack as a member variable in the Emulator class, and not as a pointer or something like that, or something the JIT compiler can do that the static C++ compiler (on O3) can't?

Answer 1

Performance

I'll get to a bit of a review, but first, since you're most interested in performance, I've done some benchmarking. In short, all evidence points towards maaartinus' theory being the cause.

Benchmark.java:

public class Benchmark {

    private static class Stored {
        private final int[] big = new int[250];

        public Stored() { }
    }

    public static void main(String[] args) {

        // Create the objects up front so we don't include allocation/construction time in the benchmark
        Stored stored[] = new Stored[1000000];
        for (int i = 0; i < stored.length; ++i) { stored[i] = new Stored(); }

        for (int n = 0; n < 100; ++n) {
            long start = System.nanoTime();

            ArrayStack<Stored> stack = new ArrayStack<Stored>(1000000);
            for (int i = 0; i < 1000000; ++i) { stack.push(stored[i]); }
            for (int i = 0; i < 1000000; ++i) { stack.pop(); }

            long end = System.nanoTime();

            if (!stack.isEmpty()) { System.out.println("This is just here to make sure nothing gets optimized out."); }

            System.out.printf("Time: %f seconds%n", (end - start) / 1e9);
        }   
    }
}

Once the JVM has warmed up and some JITing has (presumably) happened, each test takes 0.0038 seconds (with a very small variance). If the size of big in Stored is changed, this doesn't change timings since the stack stuff is still just copying a reference. Even if more references are added to Stored, this increasing the size of stored, there is still no time increase. This all makes sense: all Java has to do is copy a pointer, and the size of this pointer is fixed.

benchmark.cpp

int main() {

    // To be consistent with the Java approach, we'll create the objects up front. Noteably, this doesn't actually
    // matter since the copying of the objects is just as expensive as creation.
    // (Note: typically it wouldn't make sense for this to be dynamically allocated, but 1000000 objects was too big for
    // the stack.)
    Stored* stored = new Stored[1000000]();

    // Do the simple approach
    for (int n = 0; n < 100; ++n) {
        auto start = std::chrono::high_resolution_clock::now();

        ArrayStack<Stored> stack(1000000);
        for (int i = 0; i < 1000000; ++i) { stack.push(stored[i]); }
        for (int i = 0; i < 1000000; ++i) { stack.pop(); }

        if (!stack.isEmpty()) { std::cout << "This is here so the code doesn't get optimized out.\n"; }

        auto end = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double> diff = end - start;
        std::cout << "Time: " << diff.count() << " seconds\n";
    }
}

This was run with a few different Storeds. The first was a relatively large class:

struct Stored {
    int x[250];
};

The second was a very light class:

struct Stored {
    int x[1];
};

As a third option, the large class was kept, but rather than storing a value, a pointer was stored in the stack:

for (int i = 0; i < 1000000; ++i) { stack.push(&stored[i]); }

The timings were 0.30 seconds, 0.001 seconds, and 0.001 seconds for options 1, 2, and 3, repsectively. This is consistent with the Java theory and findings: C++ is peforming expensive copies that Java is not doing.

Benchmark Conclusions

The question now obviously becomes how to optimize your C++, and unfortunatley there's no simple solution to that without knowing a lot more about what exactly it is that you're putting into your stack. Move semantics are one option, provided your copying is expensive and you'd be happy to sacrifice the object into the stack rather than copy it.

The other option is to move away from value semantics so that copies become cheaper. If you have simple hierarchical ownership semantics (e.g. the objects being stored in the stack will always outlive the stack), this is super easy: just store pointers in the stack instead of objects. If your ownership isn't quite so simple, you would need to consider using something like heap allocation and a smart pointer. Both of these approaches are trade offs though. Smart pointers are safe but relatively expensive to copy, and raw pointers can quickly become a confusing mess if you're not very particular and consistent with your semantics. In both cases you no longer have the pleasantness of value semantics.

Answer 2

I don't consider myself a Java expert, but I can certainly comment on some things I see in the C++ implementation that you might want to address.

Fix the destructor

As has already been noted in the comments, the destructor isn't correct as written. To match with new T[capacity] it should be delete[] stack. That will make it work without crashing, but there are some other issues.

Understand object creation

In Java, as you know, objects are reference counted and automatically destroyed by the garbage collector when they're no longer needed. However, in C++, the programmer has both full control and full responsibility over both creation and destruction of the object. How this affects your ArrayStack depends on how it's being used. One way it might be used is that as each object is created and pushed onto the stack, it's now "owned" by the stack which is therefore responsible for deleting it. That seems to be the intent because the destructor destroys the objects it contains.

In that case, you need to be explicit about handing over ownership. Right now, your push looks like this:

void push(T value) { stack[pointer++] = value; }

Because it says (T value) instead of using a reference (T& value), it means that it's using pass-by-value. So even if you call push with an already-created T, this will make a new one which lives only as long as the function executes. Then it will use operator= to copy that value into the stack's version and then destroy the copy. To make this more concrete, here's an adaptation of a std::string class called MyString. Its sole purpose is to demonstrate object creation and deletion:

class MyString {
public:
    MyString() : str(), id(serial++) { 
        std::cout << "creating empty string " << id << "\n"; }
    MyString(const char *msg) : str(msg), id(serial++) { 
        std::cout << "creating string \"" << str << "\" " 
            << id << "\n"; }
    MyString(const MyString &s) : str(s.str), id(serial++) { 
        std::cout << "copying string \"" << str << "\" " 
            << id << "\n"; }
    MyString(MyString &&s) : str(), id(serial++) { 
        std::swap(str, s.str);
        std::cout << "moving string \"" << str << "\" " 
            << id << "\n"; }
    MyString& operator=(MyString &&s) {
        std::swap(str, s.str);
        std::cout << "moving string via =\"" << str << "\" " 
            << id << "\n"; 
        return *this; }
    MyString& operator=(MyString &s) {
        str = s.str;
        std::cout << "copying string via =\"" << str << "\" " 
            << id << "\n"; 
        return *this; }
    ~MyString() { 
        std::cout << "destroying string \"" << str << "\" " 
            << id << "\n"; }
    friend std::ostream &operator<<(std::ostream &out, const MyString &m) {
        return out << m.str;
    }
private:
    static unsigned serial;
    std::string str;
    unsigned id;
};

unsigned MyString::serial = 0;

Depending on how you are with C++11 (which this uses), it might not be obvious what this class does. Simply put, it has four different constructors: one for no-argument, one to copy from a const char *, one to copy from another Mystring and a "move constructor" (new in C++11). Here is an article that explains Rvalue references and move semantics, so I'll skip all of that for now. Now let's try it out with your stack:

int main()
{
    const int TESTSIZE{3};
    MyString silly{"zoom"};
    ArrayStack<MyString> stack(TESTSIZE);
    for (int i=0; i < TESTSIZE; ++i)
        stack.push(silly);
}

When I run this (with the corrected ArrayStack destructor), we get this:

creating string "zoom" 0
creating empty string 1
creating empty string 2
creating empty string 3
copying string "zoom" 4
copying string via ="zoom" 1
destroying string "zoom" 4
copying string "zoom" 5
copying string via ="zoom" 2
destroying string "zoom" 5
copying string "zoom" 6
copying string via ="zoom" 3
destroying string "zoom" 6
destroying string "zoom" 3
destroying string "zoom" 2
destroying string "zoom" 1
destroying string "zoom" 0

As you can see, there is a lot of creating and destroying happening here. The first one is the creation of silly which creates MyString instance number 0. The next three (1, 2 and 3) are due to the stack = new T[capacity]; line in your constructor. As explained above, instance 4 is created just for the call to push and is destroyed once the = operator is complete. This happens again for the next two instances, which are 5 and 6. Finally, your destructor gets automatically called at the end of main (since stack is an automatic variable that is destroyed once it goes out of scope) and finally the original silly gets destroyed. Now that we have some insight, we can see if there are ways to reduce the overhead and therefore speed things up. I'll describe things step-by-step in the hope that it makes things easier to follow.

Pass a reference to push

The first thing we can do is to pass a reference to push instead of forcing the creation of a new object.

void push(T &value) { stack[pointer++] = value; }

Here's the result of just that change on our instrumented MyString:

creating string "zoom" 0
creating empty string 1
creating empty string 2
creating empty string 3
copying string via ="zoom" 1
copying string via ="zoom" 2
copying string via ="zoom" 3
destroying string "zoom" 3
destroying string "zoom" 2
destroying string "zoom" 1
destroying string "zoom" 0

Much better already, but there's more that can be done.

Use const where practical

As @Corbin noted in a comment, the better signature for the push function would be this:

void push(const T &value) { stack[pointer++] = value; }

By adding the const keyword, we make the guarantee that the passed value will not be modified by the function. Similarly, while the original code has const for size and isEmpty, it should also have the same annotation for getCapacity:

    int getCapacity() const { return capacity; }

Use a std::vector instead of raw pointers

The underlying representation of your stack would likely benefit from being a std::vector instead of a stack. This will solve two problems. First, there's not much need to allocate a fixed capacity for a std::vector but you can specify one if you know it to improve efficiency. Second, only used values are actually initialized, so rather than constructing useless empty values, you can simply only store useful ones.

Reconsider the interface

While it makes some sense to want to return a value from peek or pop, the problem with this approach is that it might not be possible to do so. In particular, if the stack is empty, what should happen? One way to handle this would be to throw an exception.

Use smart pointers

Returning to the issue of object ownership, it seems likely that when the stack is created, you don't really want duplicate objects. If that is the case and you only want one object, you should look into using std::unique_ptr if you intend either to not use std::vector and keep the current pointer representation, or to use std::vector to keep an array of pointers.

Summary

Although the syntax is quite similar, the way that Java and C++ work can lead to very different things happening with similar looking code, as you have seen. The key point to remember is that with C++, you are responsible for memory management, while in Java, the virtual machine's garbage collection takes care of this for you. Generally speaking, this gives the edge to C++ for performance because there is no interpretation step required and the generated code is running on the real hardware rather than on a virtual machine requiring additional interpretation. Being adept in both languages takes time and effort, but is well worth the effort and you're obviously well on your way to that goal.

Answer 3

Code Review

Java

Your peek and pop methods have warning around them due to the unchecked cast. This can be fixed by suppressing the warning on each method, but an easier approach is to store an array of T and only do the cast once:

public ArrayStack(int capacity)
{
    stack = allocate(capacity);
    this.capacity = capacity;
    clear();
}

@SuppressWarnings("unchecked")
private T[] allocate(int num) {
    return (T[]) new Object[num];
}

With this, your peek and pop no longer need casts and are fully typesafe. You can also do it without a helper method, but it requires an ugly temporary variable:

public ArrayStack(int capacity) {
    @SuppressWarnings("unchecked")
    T[] tmpStack = (T[]) new Object[capacity];
    stack = tmpStack;
    this.capacity = capacity;
    clear();
}

---

Depending on usecase, it might be worth remembering that your clear() method will retain references to anything stored in the stack, making those objects ineligible for garbage collection. Depending on your object graph and how large the things being stored are, this might mean that an "empty" stack could essentially be holding a lot of memory.

---

capacity is superfluous since you can just use stack.length. Having an extra variable for something that can be derived very quickly means that you're introducing room for human error ("oh no, I forgot to update capacity correctly somewhere and now the class does crazy things!") for little advantage.

---

You should only bother with a serialVersionUID is your class implements Serializable.

---

pointer is a slightly confusing name. Maybe position instead?

C++

Bugs and errors

Your class has incorrect copy and assignment handling. Right now either operation would result in a double free and likely cause a crash once the second object was destructed.

This can be remedied by following the rule of three (http://en.cppreference.com/w/cpp/language/rule_of_three), but the real solution is to avoid unnecessary manual memory management (sometimes called the rule of 0). In this case, you can use a std::vector. As long as you make sure to size the vector up front (e.g. std::vector<T> v(capacity)), it should have the same performance as a bare array.

---

As mentioned in the comments, delete stack; should be delete[] stack; since it was allocated with new[].

---

I'm a bit wary of a custom, non-growing stack. I have a suspicion you should just be using std::stack. Best case, you preallocate enough space that it never grows. Worst case, it grows a bit and you avoid a segfault. Seems like a win-win either way.

---

Your pop implementation is not exception safe. In fact, it's actually impossible in C++ to have an exception safe pop that returns a value. What happens if the copying (or moving if you take the above suggestion) throws an exception? pointer has already been decremented, so suddenly you have no way to attempt to get at that object again once the exception has been handled.

This is actually the reason pop in the standard library doesn't return and there's instead a top method.

---

Your constuctor should be explicit. Otherwise super weird things like f(ArrayStack) {} void g() { f(5); } are valid.

---

getCapacity() should be const.

Miscellaneous

push should either take value by a const-reference.

// This brings the timings of the first case down from .30 seconds to .20 seconds
void push(const T& value) { stack[pointer++] = value; }

If you're using C++11 features, you should also provide a move option:

void push(T&& value) { stack[pointer++] = std::forward<T>(value); }

Your pop should also use move semantics if you're using C++11: void pop() { return std::move(stack[--pointer]); }

---

Peek should return a const reference. Let the consumer decide if he wants to copy before you do it for him.

Style

pointer is very confusing on the C++ side since I expect it to be a pointer.

---

To be consistent with the C++ standard library, isEmpty should be empty(), getCapacity() should be capacity(), and peek() should be top().

---

Summary

All in all, a cleaned up version might look like this:

template <class T> class ArrayStack
{
    private:
        std::vector<T> elements;

    public:
        explicit ArrayStack(int capacity)
        {
            elements.reserve(capacity);
        }

        void push(const T& value) { elements.push_back(value); }
        void push(T&& value) { elements.push_back(std::forward<T>(value)); }

        void pop() { elements.pop_back(); }

        T& top() { return elements.back(); }
        const T& top() const { return elements.back(); }

        bool empty() const { return elements.empty(); }

        void clear() { elements.clear(); }

        int size() const { return elements.size(); }

        int capacity() const { return elements.capacity(); }
};

Note that as a side effect of std::vector, this has not only some bug files and simplifications, it also has a few happy side effects:

• Pushing when full will now result in the vector growing instead of a segfault.
• Popping now destructs the item stored in the stack immediately instead of upon stack destruction. For classes that are small value wise but hold on to a lot of data, this can be very meaningful.

All in all, this cleaned up version really just brings home that you should use std::stack. Containers are surprisingly hard to get right in C++, and they often offer more functionality (sometimes in subtle ways) than your own implementation is ever going to have.