c++ - Slow Inserts Linked List multi-threading needed?

Question

In the code bellow, I'm searching for ways to optimize the speed of insertions when dealing with Millions of inserts at the time. the code runs fine but is very slow when performing large amounts of inserts. I already tried some ideas but is always slow. I guess the solution is to use Multi-threading to perform the inserts, and use a global variable "truct Node* nodeObj". I have very few/no experience with Multi-threading and Synchronization in C, C++, If you could give me an example based on the code bellow I would be very appreciated. Any additional Ideas are welcome.

The rules are: 1- In the end (after insert all numbers) the linked list must be ordered, meaning that each Node->data starts at lowest number up to the Largest number. 2 - The caller is using a for loop, this for loop cannot be started inside the Insert function. 3 - Any of the code, caller or insert function can be optimized as long as the insert function does not automatically add inserts by it self, that's the caller s job.

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>

struct Node {
    int data;
    struct Node* nextAddr;
};

struct Node* Insert(Node* p, int data);
void Print(struct Node* p);
void RevPrint(struct Node* p);

int main() {

    struct Node* nodeObj = NULL;
    printf("---------------------------------
"
        "Insert()
---------------------------------
");
    for (int i = 1; i < 1000000; i++) {
        nodeObj = Insert(nodeObj, i);
        printf(" %d", i);
    }
    printf("
---------------------------------
"
        "Print()
---------------------------------
");
    Print(nodeObj);
    printf("---------------------------------
"
        "RevPrint()
---------------------------------");
    RevPrint(nodeObj);

    printf("
Press any key to continue...");
    _getch();
}

struct Node* Insert(Node* _pToNode, int _nbr)
{
    Node *newValue = (struct Node*)malloc(sizeof(struct Node));
    newValue->data = _nbr;
    newValue->nextAddr = NULL;

    if (_pToNode == NULL) _pToNode = newValue;
    else {
        Node* pLocal = _pToNode;
        while (pLocal->nextAddr != NULL) {
            pLocal = pLocal->nextAddr;
        }
        pLocal->nextAddr = newValue;
    }

    return _pToNode;
}

void Print(struct Node* p) {

    if (p == NULL) {
        printf("
");
        return;
    }
    printf(" %d", p->data);
    Print(p->nextAddr);
}

void RevPrint(struct Node* p) {

    if (p == NULL) {
        printf("
");
        return;
    }
    RevPrint(p->nextAddr);
    printf(" %d", p->data);
}

Thank you.

Answer 1

Linked lists are unwelcome on modern machines. The L1 and L2 caches love vectors and arrays. They utterly despise linked lists. Use a std::vector, not a linked list, (and certainly not a hand-rolled linked list). Try to .reserve() enough memory in the vector to accommodate all the new stuff. Just push everything onto the back of the vector, and then sort the vector using parallel execution. C++17 can do that painlessly. std::stable_sort parallels quite nicely.