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