my list implementation is very slow

[fewdiefie]

Why is std::vector super faster than my list implementation, and how can I optimize this

template <class T>
class LinkedList
{
public:
	struct Element
	{
		Element *next;
		Element *prev;
		T *data;
		
		Element(T *data)
		    :
		    next{ nullptr },
		    prev{ nullptr },
		    data{ data }
		{
		}
		
		Element()
		    :
		    next{ nullptr },
		    prev{ nullptr },
		    data{ nullptr }
		{
		}
		
		~Element()
		{
			if (prev)
			    prev->next = next;
			if (next)
			    next->prev = prev;
			
			if (data)
			    delete data;
		}
	};
	
	LinkedList()
	    :first{ nullptr },
	    last{ nullptr },
	    size{ 0 }
	{
	}
	
	~LinkedList()
	{
		Clear();
	}
	
	void Clear()
	{
		Element *e = first;
		while (e)
		{
			Element *temp = e;
			e = e->next;
			delete temp;
		}
		first = nullptr;
		last = nullptr;
		size = 0;
	}
	
	void Add(T *data)
	{
	    
            Element *e = new Element{ data };
            

            if (!first) {
                first = e;
                last = first;
            }
            else {
	        last->next = e;
	        e->prev = last;
                last = e;
            }
		
            size++;
	}

        Element *Iterate(bool reset = false)
        {
            if (reset) { iterator = first; }
            else {
            iterator = iterator->next;
            return iterator;
            }
        }
	
private:
	Element *first;
	Element *last;
        Element *iterator;
	int size;
};

[dutch]

You should've posted the complete program that you ran for testing the timings since it partly depends on the pattern of access.

There is nothing in the code you've shown that would make your linked list particularly slow.

However, the data in a list is more spread out than that in a vector, so a vector has more locality of reference. The more data that can fit into the cache the faster the code will generally run.

Hear it from the horse's mouth: https://www.youtube.com/watch?v=YQs6IC-vgmo

One thing I am a little worried about with your code is that you have the Element dtor adjusting pointers that reside in other elements. I would rather see such manipulations in a LinkedList member function.

[fewdiefie]

thanks for your quick reply, i tested using this piece of code

int main()
{
    LinkedList<int> list;
    start = clock();
    for (int i = 0; i < 1000000; i++)
        list.Add(new int);
    end = clock();

    cout << end - start << endl;

    vector<int> v;
    start = clock();
    for (int i = 0; i < 1000000; i++)
        v.push_back(0);
    end = clock();

    cout << end - start << endl;
}

One thing I am a little worried about with your code is that you have the Element dtor
 adjusting pointers that reside in other elements. I would rather see such manipulations in a
 LinkedList member function.

it does set the pointers based on a condition, it's safe and btw the Element destructor only gets called when an element is explicitly removed or the list's destructor is called


I want to optimize data insertion and not access

[dutch]

Why would you think the linked list wouldn't be blown out of the water in that code?
It has far more operations to perform in every iteration of the loop.

It needs a memory allocation every time. INCLUDING FOR THE STUPID INT DATA ITSELF!
And it has to set a couple of pointers every iteration, too.

The vector reallocates only when it runs out of space. No pointers. No extra allocation for the int.

Your linked list hasn't a chance in hell in this situation.

[fewdiefie]

so how can I optimize it for fuck sake

[dutch]

What the fuck are you talking about?
Use a vector.

[fewdiefie]

I want to make my LinkedList class faster, is there any way to do that

[dutch]

Choosing the right data structure for the job is the most important part. I have no idea what your real use scenario is. In the code you've shown, use a vector.

However, if for some reason you really need to make it faster then all you can do is change it to a singly linked list and make data int instead of a pointer-to-int.

[jlb]

Why are you comparing your list to a std::vector?

Why not compare your list to a std::list?

By the way with today's PC hardware a vector will probably outperform any list except in rare circumstances.

If you must continue then you need to profile your code to see where the bottlenecks are located.

[Repeater]

I want to optimize data insertion and not access

In typical use, to optimise for insertion, don't use a linked list. They're typically very slow for insertion. They are also slow for access and slow for removal of an item.

I want to make my LinkedList class faster, is there any way to do that

Don't create nodes using new. Create all the nodes in a single vector of blank nodes, before you start using the list. Keep all the nodes together in memory.

This is quite awkward sometimes; why do you need a list? A vector is typically faster for access, faster for insertion, faster for removal, just faster all round.

[fewdiefie]

thank you so much

A vector is typically faster for access, faster for insertion, faster for removal, just faster all round.

I worked with C++ for 3 years now but I'm still unfamiliar with the STL, I didnt know how vectors exactly work XD, thanks for the information

I have implemented this basic Vector class that suits my needs and it works 2 times faster than std::vector, is it safe to use delete with C's malloc and realloc though

template <class T>
class Vector
{
public:
    Vector() :data{ nullptr }, size{ 0 }, capacity{ 0 } {}
    ~Vector() { delete[] data; }
    
    void push_back(const T& t)
    {
        if (!data)
        {
            capacity = 1;
            data = static_cast<int*>(malloc(sizeof(T)));
        }
        else if (size == capacity)
        {
            capacity *= 2;
            data = (int*)realloc(data, sizeof(T) * capacity);
        }
        
        data[size] = t;
        size++;
    }
    
    T &operator[](int index) { return data[index]; }

private:
    T *data;
    int size;
    int capacity;
};

BTW I'm using this to hold game entities

[salem c]

> data = (int*)malloc(sizeof(T));
> data = (int*)realloc(data, sizeof(T) * capacity);
No and no.
malloc and realloc do not call constructors. Fine for your PoD 'int', but you're hosed if you try and pass an actual class into your template.

And your realloc risks leaking memory as well.
If it returns NULL, then the (now obliterated) data still points to the old memory.


> delete[] data;
And definitely not.

malloc/realloc/calloc should be matched with free.
new should be matched with delete.
new[] should be matched with delete[].
You can't just pick and mix, they have to match.

[fewdiefie]

If it returns NULL, then the (now obliterated) data still points to the old memory.
If it returns NULL, then data = NULL not old memory

so is there any way to do this with new and delete

[Ganado]

and it works 2 times faster than std::vector,

If a race car is on fire and explodes, does it really matter that it's beating the other car that isn't on fire?
Also, I would actually want to see your benchmarking before believing anything like that.

[fewdiefie]

@Ganado why would my class explode LOL, if you understand c++ code than you would see that it is completely safe. except for the ralloc and malloc that I'm currently looking at.

[TheToaster]

works 2 times faster than std::vector,

This is most definitely a lie and I highly doubt you could provide benchmarks to show this.

[dutch]

Toaster wrote:

This is most definitely a lie

Not necessarily.
realloc can potentially be much faster than C++ reallocations since C++ always has to copy the data to new memory whereas realloc can just extend the memory that it already has. (I believe this is the case.)
However, in real-life use cases, even the realloc would need to move stuff around now and then.

[dutch]

fewdiefie wrote:

If it returns NULL, then data = NULL not old memory

salem is saying that if the realloc fails it returns NULL.
If you mindlessly assign this to data then you will lose the previous data.

[Ganado]

Also, from what I've seen, C implementations can often be faster than equivalent C++ implementations for things when optimization is turned off.

However, when optimization is turned on, C and C++ perform much more equally.

For example, here is the results of your benchmark for me:

>main
0.001
0.001

[TheToaster]

Well I wasn't saying that realloc being faster is a lie, I was saying his claim that his Vector class works 2 times faster than std::vector is most likely a lie unless he can provide exact benchmarks that show it is twice as fast. "2 times faster" than an std::vector is a very specific number and I'm gonna need some proof before I can believe that.