Idea for virtual memory allocator: yea or nay? [verdict:nay]

[nexos]

An O(n) algorithm would be like this

Code: Select all

for(int i = 0; i < num; ++i)
{
    do something;
}

An O(1) algorithm would be like this

Code: Select all

do something;

The difference, an O(1) algorithm always executes in the same amount of time no matter what. It is also much faster in must circumstances, as a block of code will execute once only. An O(n) algorithm is a bitmap, for example, you loop through every bit in the map to find a free one. A free list is a O(1) algorithm, it has its info right there. No looping needed.
Graphed, you can see the difference. Here are some links to what these algorithm types look like graphed

[eekee]

Not parameters, but rather finding a place to put the requested allocation. As a simple example, if a free list gets very long, it could take a long search to find a suitably-sized entry, and there's poor cache locality all the way.

[neon]

Hi,

This is what I like about free stacks as they can be written as O(1).

[nexos]

Hi,

This is what I like about free stacks as they can be written as O(1).

Yep. I am trying to make most of my system use O(1) algorithms, hoping that might be useful if I decide to support hard real time, and is altogether better for performance.