whats a offset allocator?
https://github.com/sebbbi/OffsetAllocator which has links to a pertinent paper at the end of that page.
That doesn't explain anything.
And the linked paper doesn't even contain the word 'offset'.
Fast, simple, hard real time allocator for Rust
51–60 of 61 posts
Re: Fast, simple, hard real time allocator for Rust
#52Why is this hard realtime in the face of arbitrary allocations and deallocations? These dots aren't connected anywhere within two links distance from the given URL.
Re: Fast, simple, hard real time allocator for Rust
#53Earlier quoted context omitted.
I did this too! Except it was based on the original TLSF paper (on which this work is based) as I wasn't aware of that offset allocator. > I'm also curious about making something like this work as a general purpose allocator (as alluded to by the README). In a general purpose allocator, you can just store allocation metadata next to a payload so the lookup from a pointer address becomes O(1). The original TLSF algori…
Have you published your code to GH, by any chance?
Offset allocator: https://github.com/yvt/xalloc-rs/blob/master/src/tlsf.rs Don't mind the mess, it's one of my earliest works in Rust.
General-purpose allocator: https://github.com/yvt/rlsf
Re: Fast, simple, hard real time allocator for Rust
#54Earlier quoted context omitted.
This function is O(1): https://github.com/scotts/streamflow/blob/master/streamflow.... . All other tree operations are also constant, because the fact that it is a 3-level tree is hardcoded. Asymptotic bounds are useful when your input can grow arbitrarily large. When your input is fixed, the bounds become less useful and you should focus on the particulars of your case. In the case I'm presenting, the work done trav…
> This function is O(1) I think I addressed that in my comment, but to be more explicit, this function is O(1) too: size_t find_sorted(void* object, void** list, size_t size) { for (size_t i = 0; i object) return i; } return SIZE_MAX; } If O(1) cannot distinguish your function from this function, what is its informational value? > Asymptotic bounds are useful when your input can grow arbitrarily large But your inputs…
I'm really not sure what you're overall point here is. Yes, I agree with you. Your function is O(2^64) which is technically O(1). Your point, which I agree with, is that's completely useless information. It does not help our understanding of performance at all. Calling such a function O(1) is technically true, but both misleading and not informative. What I'm not clear on is how that relates to the discussion we're having here.
The original poster said they wanted a O(1) solution to a problem. I presented one. That solution happens to be based on a data structure whose algorithms are, in the general case, O(log n). But we're not dealing with a general case, we're dealing with a specific case. And because of that specific case, we can write algorithms that are O(1). Unlike your example, these algorithms have a very small n; 3, to be exact. That is meaningful to describe as O(1) in this case because we can reduce the work down to a small constant.
Re: Fast, simple, hard real time allocator for Rust
#55Earlier quoted context omitted.
> This function is O(1) I think I addressed that in my comment, but to be more explicit, this function is O(1) too: size_t find_sorted(void* object, void** list, size_t size) { for (size_t i = 0; i object) return i; } return SIZE_MAX; } If O(1) cannot distinguish your function from this function, what is its informational value? > Asymptotic bounds are useful when your input can grow arbitrarily large But your inputs…
This is O(n) because you're still doing the i comparison, even though you've moved it out of the for loop.
For almost all n (size), the function runs for MAX_SIZE steps, since almost all numbers are greater than MAX_SIZE. And it never runs for more than MAX_SIZE steps.
Re: Fast, simple, hard real time allocator for Rust
#56Earlier quoted context omitted.
That doesn't mean that naive single-threaded code is necessarily interrupt-safe. If the allocator is interrupted and the interrupt service routine needs to make use of the allocator's data structures for any reason there could very much be a conflict. This particular algorithm is focused on GPUs, so I'm not clear on the applicability. However I did want to clear up the idea that there are no concurrency concerns for…
The presence of interrupts is basically equivalent to not being single threaded, though. There are true single-threaded environments, it's just limited to userspace processes that don't handle signals.
It is even worse: re-entrancy safe is a different property than thread-safe. For example you can't use mutexes to guarantee mutual exclusions with interrupts.
Some algorithms are both thread safe and reentrancy safe, but generally this is not the case.
Re: Fast, simple, hard real time allocator for Rust
#57Earlier quoted context omitted.
> This function is O(1) I think I addressed that in my comment, but to be more explicit, this function is O(1) too: size_t find_sorted(void* object, void** list, size_t size) { for (size_t i = 0; i object) return i; } return SIZE_MAX; } If O(1) cannot distinguish your function from this function, what is its informational value? > Asymptotic bounds are useful when your input can grow arbitrarily large But your inputs…
I'm really not sure what you're overall point here is. Yes, I agree with you. Your function is O(2^64) which is technically O(1). Your point, which I agree with, is that's completely useless information. It does not help our understanding of performance at all. Calling such a function O(1) is technically true, but both misleading and not informative. What I'm not clear on is how that relates to the discussion we're h…
My overall point is that neither your function or my function are actually O(1). Whenever you see the notation O(...), there is an implicit context "As input size n grows arbitrarily, ...". You can check the formal definition on Wikipedia.
The cost function for both our functions is not defined for arbitrary n, because they both stop working when input size crosses a threshold. So the O(1) notation is not well-defined in this case.
Now you could come up with a different formal definition for O(1) for bounded input sizes, which is fine, but I don't think you can find one that makes your function O(1) and my function non-O(1). So it would be not be a meaningful definition in this case.
Ultimately, you're using O(1) colloquially. In your words, calling my function O(1) is misleading while it is fine for yours because the constant is "small". "Small" is a subjective term, while O(1) is a formal term.
If your definition hinges on a subjective characterization, why not just say "it's fast", instead of incorrectly using a technical term?
(If we really want to be pedantic, there is really no such thing as "constant-time" when accessing memory, a TLB miss for example will make the CPU traverse a tree; a page fault can execute arbitrary code).
Re: Fast, simple, hard real time allocator for Rust
#58Earlier quoted context omitted.
I'm really not sure what you're overall point here is. Yes, I agree with you. Your function is O(2^64) which is technically O(1). Your point, which I agree with, is that's completely useless information. It does not help our understanding of performance at all. Calling such a function O(1) is technically true, but both misleading and not informative. What I'm not clear on is how that relates to the discussion we're h…
My overall point is that neither your function or my function are actually O(1). Whenever you see the notation O(...), there is an implicit context "As input size n grows arbitrarily, ...". You can check the formal definition on Wikipedia. The cost function for both our functions is not defined for arbitrary n, because they both stop working when input size crosses a threshold. So the O(1) notation is not well-define…
Ah, in my context, N is the number of live allocated objects that the memory allocator knows about. If you use a data structure like a red-black tree to track the metadata, the work you do traversing and maintaining the tree will grow log N with the number of live allocated objects you're tracking. The radix tree specialization I presented is constant with respect to the number of live allocated objects.
Re: Fast, simple, hard real time allocator for Rust
#59Earlier quoted context omitted.
https://github.com/sebbbi/OffsetAllocator which has links to a pertinent paper at the end of that page.
That doesn't explain anything. And the linked paper doesn't even contain the word 'offset'.
I mean you could presumably read the code.
It looks like the general idea of TLSF is an array of second level arrays, where the second level arrays hold blocks of fixed size, and in TLSF those fixed sizes for the secondary arrays increase as powers of 2, and in this so called offset allocator the secondary level arrays use a more complex size statistically chosen. Allocation requests seemingly return an offset into a second level array.
Kinda uncommented code, to your point, makes it not obvious.
Re: Fast, simple, hard real time allocator for Rust
#60Earlier quoted context omitted.
> It just makes it O(n) where n := 64 That's O(1). > The LZCNT operation itself is a loop over all bits That's not how circuits work. You can easily make a circuit of O(log n) depth that returns base-2 encoded index of the first 1 bit in a n-bit register. But since n is just 64 here, you're looking at a circuit of AND/OR depth ~8, so it's no surprise that modern CPUs can compute the LZCNT / TZCNT of a 64-bit integer…
> That's O(1). A loop over 2^64 elements is also O(1), but I don't think people are ok to label every program that can run on a 64 bit pc as O(1).
You should really refresh yourself on Big-O notation.