Comment Re:I don't currently use Rust (Score 1) 160
heapless is quite useful in many contexts, yes.
As for what my design goals are, it's a pretty typical LRU map. I assumed that the name would tell you what the purpose is, but perhaps not. Please excuse me for belaboring if you are already familiar with these concepts; I don't know what you know, so I figure it's better to be clear. If you do, skip the next paragraph.
An LRU (Least Recently Used) cache is a cache that has a fixed maximum size and when a new item is added that would cause it to exceed that upper bound, it discards the "oldest" entry in the cache, where "oldest" is defined as least-recently used. An LRU map is similar but it is "primary storage" not cache, but still with a fixed capacity so when you try to put more in it than it can hold it has to discard something, and it does that by discarding the least-recently used item.
In my case, I'm writing code that services client code running on other CPUs in the same SoC. The client transactions are moderately long-running, each involving a sequence of requests delivered over the course of a few seconds, though some sessions legitimately go much, much, longer, and each such session requires me to track a non-trivial amount of state, not so much for efficiency as for security; I can't hand the internal state back to the caller because that might allow an attacker to mutate it or roll it back (if rollback weren't a concern, I could outsource a MACed copy of the state). I keep the operation state in a map structure, keyed by an operation ID. But clients can die and clients can misbehave, so I can't safely rely on the clients to always send me the termination message that allows me to clear the operation state.
So, I need some way to ensure that my map doesn't fill up with stale operation data, preventing new operations from being started. LRU eviction is a cheap and effective method. But this means that sometimes clients are going to send a request for an operation that I have evicted, so I have to return an error message. I could just always say "Operation ID not found", but then clients have no way to distinguish between cases where they just waited too long and cases where I suffered a failure or was reset. The clients often respond to these different failure modes in different ways.
For that reason, I keep a "recently-evicted" list -- but that also has to have a fixed size limit. In practice, my recently-evicted list consists of two lists, an "old generation" list and a "new generation" list, both with fixed size limits. Every time an operation is evicted, it's added to the "new generation" list. When the new-gen list is full, I move it to the old-gen list (in practice, I really just change which list is considered new and which old; no need to copy it). This is a cheap way to "age" the eviction records, without actually having to track their age in an LRU fashion (which would ~double the per-entry storage required, halving the number of evictions I can track). When a request for an unknown operation ID comes in, I search both lists to see if the ID has been recently evicted. If so, I remove the ID from the list and report the error to the caller. The reason for removing is to make space for a new eviction record, to maximize the scenarios in which I can notify clients.
Regarding your comment about encapsulation being overused... this is not such a case. The purpose of encapsulation, properly applied, is invariant maintenance, and there are some important invariants that have to be maintained for the LRU map to work. One of those is that insertion must execute the eviction logic, so even if I could move the map out temporarily, that would create an opportunity for bugs if the calling code does not correctly handle eviction and maintenance of the recently-evicted list. Another (less crucial, but still important) is that the recently-evicted list should only contain entries for clients that haven't yet been notified.
That said, there actually a good argument that the `recently_evicted` method is conceptually non-mutating and I should use interior mutability. Either that or I should rename it to "remove_eviction_record", so it's clear that it is inherently a mutating operation. I will do one of those two things on Monday -- thanks for helping to improve my code. I would prefer the rename for clearer semantics, but interior mutability will allow me to avoid the extra map lookup, so I'm leaning that way.
One other comment about something you said, which you might find interesting: You said that in Rust, moves are cheap. This isn't really true. More precisely, it isn't any more or less true in Rust than in any other language. Regardless of language, when you move data, you must copy it, and you're paying the cost of that copy. What makes moves so useful in Rust is not that they're cheaper in time or space but because of the marvelous move invariant that is enforced by the compiler. Namely, that moved-from values cannot be referenced.
To see how important that is, compare with C++, which also allegedly supports move semantics. The modern C++ style makes heavy use of move semantics. But C++'s move semantics are broken in a way that makes them less efficient and more difficult to use safely, and that's because C++, like C, always allows code to reference any value that has a name. That means that moved-from values can be referenced, which means it's critical that moved-from memory not be left in an invalid state when interpreted under the invariants of its type. So the rule is that moved-from C++ objects must be left in a "valid but unspecified state". In practice, this translates into the move ctor/optor having to do work in the moved-from memory, zeroing pointers and whatnot, in order to ensure that what's left behind upholds the invariants of the type, and it means that C++ structs that support move-from must have some valid but not semantically-significant state they can be in.
What makes Rust's move semantics easier to work with, more efficient and safe is that there's no need to ensure that the moved-from memory is in any kind of valid state, because the compiler will not allow the moved-from memory to be accessed. Another way to think about it is that the moved-from memory no longer has any type, so no longer has to maintain any type invariants. It's fine to leave behind bit patterns that used to be pointers or whatever, because those bit patterns will never be used.
Coming from 35 years of C++ programming, this was something of a revelation to me when it hit me a few months ago. And it's the real meaning of "moves are cheap", which isn't a comment about time or space, but a comment about invariant maintenance.
