2
\$\begingroup\$

I took a challenge from a web site. I aim to have a runtime performance as good as possible. My solution was accepted, though I think it is not the most efficient because I saw others having a faster solution. Are there dos and don'ts in regard to C++ programing in order to try to get the best performance possible. This question is about coding optimally. I have no means to tweak around with compiler options or so.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* res = NULL;

        if (size(l1) < size(l2)) 
            res = add(l1, l2);
        else
            res = add(l2, l1);

        return res;
    }

private:

    /**
     * Input: A list
     * Output: size of the list
     */
    static int size(const ListNode *l) {
        int size = 0;
        while(l != NULL)
            ++size, l = l->next;
        return size;
    }

    /**
     * Input: Two lists l1 and l2 with size(l1) <= size(l2)
     * Output: result list
     */
    ListNode* add(const ListNode *l1, const ListNode *l2) {
        ListNode *head, *l;
        register bool carry_over = false;
        int x = l1->val + l2->val + carry_over;

        if (x > 9) {
            carry_over = true;
             x -= 10;
        } 
        head = l = new ListNode(x);  
        l1 = l1->next;
        l2 = l2->next;

        while (l1 != NULL) {
            x = l1->val + l2->val + carry_over;
            if (x > 9) {
                carry_over = true;
                x -= 10;
            } else
                carry_over = false;
            l = l->next = new ListNode(x);
            l1 = l1->next;
            l2 = l2->next;
        }

        while(l2 != NULL) {
            x = l2->val + carry_over;
            if (x > 9) {
                carry_over = true;
                x -= 10;
            } else
                carry_over = false;
            l = l->next = new ListNode(x);
            l2 = l2->next;
        }

        if (carry_over)
            l->next = new ListNode(1);

        return head;
    }

};
\$\endgroup\$
3
\$\begingroup\$

Eliminate size

The size function is not useful. Imagine if one list contains 1 element and the other contains a million. If you're lucky you might traverse the shorter list first, and use that size to stop traversing the second list early when possible.

Instead of trying to check the size first, you could adjust the main loop in add from this:

while (l1 != NULL) {

to this:

while (l1 != NULL && l2 != NULL) {

and add this condition after, to prepare for the second loop:

if (l1 != NULL) {
    l2 = l1;
}

More natural int carry

Instead of bool carry_over, it would be more natural to have an int carry, with 0 or 1 as values. The end result is the same, but more natural, less surprising.

Duplicated adding logic

The logic of adding is duplicated several times:

  • For the first pair of elements
  • For the pairs of elements while exist
  • For the remaining elements of the longer list

You can easily eliminate the first, by using a dummy node to mark the head of the new list. The value of this node will not be used, but dummy->next will point to the first element. In addition, this little trick will make the implementation more robust, and handle the case when one of the lists is empty (null).

Declare variables in the smallest scope

There's no need to declare x at the top. You can declare it inside the loops where needed.

Naming

Lowercase l is one of the worst possible names for a variable. In some fonts it might look like the number one. Almost any name would be better than that. For example node.

Braces

It's recommended to use braces always, even with single-statement if.

Suggested implementation

Applying the above suggestions, the implementation becomes:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        return add(l1, l2);
    }

private:

    /**
     * Input: Two lists l1 and l2 with size(l1) <= size(l2)
     * Output: result list
     */
    ListNode* add(const ListNode *l1, const ListNode *l2) {
        // dummy node, helps simplify the code a bit
        ListNode dummy(0);
        ListNode *node = &dummy;

        int carry = 0;

        while (l1 != NULL && l2 != NULL) {
            int x = l1->val + l2->val + carry;
            if (x > 9) {
                carry = 1;
                x -= 10;
            } else {
                carry = 0;
            }
            node = node->next = new ListNode(x);
            l1 = l1->next;
            l2 = l2->next;
        }

        if (l1 != NULL) {
            l2 = l1;
        }

        while (l2 != NULL) {
            int x = l2->val + carry;
            if (x > 9) {
                carry = 1;
                x -= 10;
            } else {
                carry = 0;
            }
            node = node->next = new ListNode(x);
            l2 = l2->next;
        }

        if (carry) {
            node->next = new ListNode(1);
        }

        return dummy.next;
    }
};

Speed

I suppose the exercise comes from here. I don't know how to make this faster. I submitted your original code, and some variations, but the result appears to be randomly within 36-56ms. At 36ms it beats 64% of submissions, at 40ms it beats only 18% of submissions. But I don't think speed is important at all. The time complexity of your algorithm is \$O(n)\$, and I don't think it's possible to solve this problem faster than that. Any speed optimizations at this level are just micro-optimizations, neither relevant nor interesting.

\$\endgroup\$
  • \$\begingroup\$ Excellent answer. Thank you very much. And you are right, the exercise came from that web site. I use it to improve my coding skills, as I am preparing to get certified in C++ sooner or later. \$\endgroup\$ – Ely Apr 30 '16 at 12:13
  • \$\begingroup\$ The only thing I would change is the dummy. Rather than dynamically allocating it make it an automatic object (it's not returned). \$\endgroup\$ – Martin York Apr 30 '16 at 17:31
2
\$\begingroup\$

To fully comprehend this review, you should know what is aliasing, data on the heap, data on the stack and difference in time accessing data on CPU register and RAM.

Main reasons why your code is slow

Aside from algorithmic optimizations. Firstly, you're using dynamic allocations, which is much slower than allocation on stack. Secondly, first reason causes probably very frequent cache misses. Everytime there is a cache miss, CPU have to reload it from RAM (around 100 times more than accessing Register of CPU (L1 cache)).

Optimization

Use memory pool covered with custom allocator. Depending on how many list nodes you have, you may even get away with memory on the stack. Types of allocators, as well as many implementation hints can be found in the talk by Andrei Alexandrescu. I recommend you having stack allocator for the beginning, and then after profiling you can choose more complex one. This will allow you to use std::list or std::forward_list. You can pass allocator as template parameter. Here is the link for allocator concept.

Possible implementation

Here is the most simple allocator which stores your list in contiguous memory.

#include <cstdlib>
#include <exception>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Allocator
{
    const size_t threshold = 200;
    ListNode* pool;
    ListNode* target;
public:
    Allocator(): pool(nullptr), target(nullptr)
    {
        pool = (ListNode*)std::malloc(sizeof(ListNode)*threshold);
        target = pool;
    }

    ListNode* allocate(int x)
    {
        if (target > pool + threshold)
        {
            throw std::bad_alloc();
        }

        *target = ListNode(x);
        return target++;
    }

    ~Allocator()
    {
        free(pool);
    }
};

Reasons why it is faster

  1. In this talk Herb Sutter says that contiguous memory gives us next level of cache, which means that access to memory on RAM will get faster in subsequent calls. Just skip part about performance per dollar, watt, etc of the talk.
  2. Dynamic memory allocation is system call, which incurs overhead. Multiple calls to allocate memory may further slow down the code, that is why there is only 1 call to dynamic allocation. Consider adjusting threshold member to suit your needs.

Using this Allocator, you can replace every call to new by call to Allocator::allocate().

Answer for your question

  1. Avoid dynamic allocations when possible, keep objects on the stack. Allocations on the stack are very fast, because it actually involves stack data structure, very simple form of which I've attached as allocator. It stores contiguous memory. But stack given by the system is usually very small (1MB).

  2. Do less work. Consider redesigning your class to store size explicitly, in member variable. Trading memory for speed sometimes may be hard choice, but you need to do it. In this case, if you're not strict on memory by problem statement, store size in member variable. C++ coding standards by Herb Sutter has chapters for optimization, which introduces premature optimization and premature pessimization. It is really important to know when avoiding optimization becomes pessimization.

  3. Algorithmic optimization is not always actual performance benchmark. Keep data local, small or at least contiguous if possible.

Other tips you can find on stackoverflow (For example this, and this).

Complete code

#include <cstdlib>
#include <exception>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Allocator
{
    const size_t threshold = 200;
    ListNode* pool;
    ListNode* target;
public:
    Allocator(): pool(nullptr), target(nullptr)
    {
        pool = (ListNode*)std::malloc(sizeof(ListNode)*threshold);
        target = pool;
    }

    ListNode* allocate(int x)
    {
        if (target > pool + threshold)
        {
            throw std::bad_alloc();
        }

        *target = ListNode(x);
        target++;
    }

    ~Allocator()
    {
        free(pool);
    }
};

Allocator allocator;

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* res = nullptr;

        if (size(l1) < size(l2))
        {
            res = add(l1, l2);
        }
        else
        {
            res = add(l2, l1);
        }

        return res;
    }

private:

    /**
    * Input: A list
    * Output: size of the list
    */
    static int size(const ListNode *l) {
        int size = 0;
        while (l != nullptr)
            ++size, l = l->next;
        return size;
    }

    /**
    * Input: Two lists l1 and l2 with size(l1) <= size(l2)
    * Output: result list
    */
    ListNode* add(const ListNode *l1, const ListNode *l2) {
        ListNode *head, *l;
        bool carry_over = false;
        int x = l1->val + l2->val + carry_over;

        if (x > 9) {
            carry_over = true;
            x -= 10;
        }

        head = allocator.allocate(x);
        l1 = l1->next;
        l2 = l2->next;

        while (l1 != nullptr) {
            x = l1->val + l2->val + carry_over;
            if (x > 9) {
                carry_over = true;
                x -= 10;
            }
            else
            {
                carry_over = false;
            }
            l = l->next = allocator.allocate(x);
            l1 = l1->next;
            l2 = l2->next;
        }

        while (l2 != nullptr) {
            x = l2->val + carry_over;
            if (x > 9) {
                carry_over = true;
                x -= 10;
            }
            else
            {
                carry_over = false;
            }

            l = l->next = allocator.allocate(x);
            l2 = l2->next;
        }

        if (carry_over)
        {
            l->next = allocator.allocate(1);
        }

        return head;
    }

};

Side notes

You're following, I think, the most famous anti pattern in OOD - class with no state. Consider using free functions, because it is not Java where you can't have them.

Consider forgetting register keyword. Compilers do better register optimization than us.

Be explicit. Some of your function names may do surprising things for users. For example, add member function, in my opinion, wouldn't create new list, but add first to the second.

Use nullptr when you want null pointer. For compiler, NULL is, first of all, int.

Use {} even if there is one expression. It will make code more explicit, and probably avoid programmer to make mistakes in the future.

Static size() member function is really strange. Consider redisigning.

I know that exception safety and performance may contradict, but adding exception safety to sufficient extend would be better. Exceptions incur no overhead when there is no exception.

\$\endgroup\$
  • \$\begingroup\$ I am very impressed by your comprehensive answer. Thank you so much for your time. I'll take you answer and see if I can improve in the benchmark. \$\endgroup\$ – Ely Apr 30 '16 at 12:09
  • \$\begingroup\$ Please note that if you redirect your next variable at least once, you may get huge slowing down when the next variable is used. If you're redirecting frequently, then the Allocator becomes irrelevant, but if there is no redirection, then performance will be around std::vector. \$\endgroup\$ – Incomputable Apr 30 '16 at 12:26
  • \$\begingroup\$ This has a serious problem though: for a list of more than 200 elements, it fails completely. It's hardly far-fetched to guess that the site is likely to have tests with lists longer than that. \$\endgroup\$ – Jerry Coffin Apr 30 '16 at 16:24
  • \$\begingroup\$ Lots and lots of good advice in general. But very few relevant to the question. \$\endgroup\$ – Martin York Apr 30 '16 at 17:02
  • \$\begingroup\$ @LokiAstari, I did my best, but I will a freshman on bachelor next year, so this is my limit for now. \$\endgroup\$ – Incomputable Apr 30 '16 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.