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.

A modern version of GTA London would be the absolute dream. Been long enough now, you could set it in the nineties and have the same retro value to it!

... why unions aren't much more common among technology workers. Especially given what you hear about the videogame industry in particular, with that mad 'crunch time' culture in which workers are ruthlessly, well, crunched. I'd always ask, well, what does your union say about it? And what do you know, there isn't one, how about that.

Nice to hear of some progress being made, then. I suppose the risk with this for the rest of us is that GTA 6 might be late to release, but, uh, at this point I think we're over that

Since Windows never supported this unusual 32/64-bit hybrid, it will have no impact on WINE.

It's actually kind of a cool idea, though. To someone like me who grew up on 8-bit and 16-bit architectures and is regularly taken aback at the size of data structures on 64-bit platforms -- 16 bytes just for a pointer and a length? -- being able to cut those down while still being able to run at full speed [*] on modern hardware sounds really useful.

[*] Assuming it's really full speed. I suspect there's some overhead.

Sure, if you want to run a system with hundreds of known vulnerabilities. Better keep it airgapped.

Er, actually, the above is incorrect and was a result of my contrived test example. With the real data structures there is no risk of anyone moving them because the code that creates them returns *only* a &'static mut. Effectively, no stack frame ever has ownership of the structures, so there is no risk of them being moved. This is all pretty obvious, actually, and essentially necessary. If there is no heap then everything is either stack-based or something akin to a global.

I checked and, indeed, trying to "move" the "hashmap" generates code to copy enough stuff onto the stack to blow it. I'm going to look into using Pin to let the compiler know that none of that stuff is moveable. Thanks!

Yeah, so you apparently missed that I have no heap and the "hashmap" isn't actually a hashmap... and it's actually in the same not-really-moveable space as the data it holds. It would be interesting to look into what would happen if I tried to move it; I think the compiler doesn't actually know that it's not moveable and would generate code to copy it to the stack. That would be more expensive than copying the "contained" data item, since it actually owns its lookup tables by value, rather than holding pointers to heap allocated structure.

As I said, your big-system biased intuitions don't really hold here.

Moving something out of a hashmap and then back into it isn't cheap. I mean, both operations are O(1), but that's amortized and hides significant overhead. I think it's well worth returning a &mut to avoid that, even in the common, std case. In the my noalloc case, it's considerably more complicated than that: The referenced memory isn't really moveable (and it's not really a hashmap). In practice, it would be "copy the data to the stack, leaving the original in-place, then make sure to copy the mutated version back to the original location". The stack consumption of that approach would be worrisome.

This is where the big-system biases of some of the Rust community work against it, and what fuels the certainty of C programmers that C is the right language for tiny devices. In C there would be no question -- you'd just look up the data in the map and return a pointer to it. Very efficient, no needless waste of several hundred bytes of precious stack space or any need to find some other memory region to copy it into. You say that "moves in Rust are cheap" but whether that's true is extremely context-dependent, and it's basically always the case that a pointer is even cheaper.

Unfortunately, the risks of the C approach are very well-understood, and my point in the post with which I entered this discussion was that Rust can be just as good for space and cycle-efficient low-level code as C while also providing significant security and safety benefits. Your arguments would seem to undermine my point about Rust's utility, except that your big-system biases are not, in fact, universal in the Rust ecosystem. There are plenty of people who understand the constraints of writing code on a device with 64K total RAM and a 1K stack who are writing Rust code and ensuring that the language is a good fit.

Not insane at all, just uninterested in the well-being of anyone other than himself.

If this happens, Trump will end up being in charge of deciding which companies get the plutonium, and those that do the best job of making Trump feel, er, appreciated, will get the nod. Also, I expect Trump to address safety concerns by setting up a multi-billion dollar fund of taxpayer money to address any necessary cleanups or other issues, a fund that is under his sole ultimate control, without congressional or any other oversight (c.f. Venezuela oil fund, "anti-weaponization fund", etc.). Maybe it'll have confidential quarterly reports issued to the NRC's board of directors (which is traditionally independent but now thoroughly controlled by Trump thanks to SCOTUS' allowing Trump to fire anyone in the executive branch and Trump's immediate action to fire Christopher Hanson as chair of the NRC board and replace him with a lapdog).

To be fair, it arguably should always had had that disclaimer. They avoiding needing it by saying they were just providing links and it was on those web sites and their users to deal with any inaccuracies... but everyone knew that most users just took whatever the top link said as definitive truth.

True. So a smallish (though big enough to produce a visible shockwave that expanded for at least hundreds of meters) detonation followed by a much larger deflagration, perhaps.

Hmm. I think you misunderstood the problem (possibly I over-simplified the toy version). In your "works" function, you're evicting an already-evicted entry? What? Also, you're still doing two map lookups, so you've (a) used my two-lookup solution (b) violated encapsulation by exposing the evict function and (c) returned a weird error to the caller... you're telling the caller you couldn't find their item to evict, when they were trying to retrieve something not evict something.

As for not mutating in a match guard, the mutation is an internal detail, not part of the public interface.

Yes, this argues for maybe using a RefCell for internal mutability to avoid the semantically-inaccurate exposure of that internal mutation through the &mut self on recently_evicted(). That's a valid point and a better solution. I should probably get more comfortable with RefCell; for some reason the concept rubs me the wrong way, though I don't have any problem with the comparable C++ construct (a mutable field).

Another option is to forgo the optimization of removing the already-reported eviction record from recently_evicted. This isn't just a performance optimization, though, it's to maximize the number of callers who are informed about why their attempted operation failed while keeping the space strictly bounded (it's not actually a Vec in the real code, nor is the HashMap a std::HashMap -- this code runs on a tiny microcontroller with no heap). There's quite a bit more to it than my very-simplified example showed -- but every way of doing it requires mutating the recently_evicted record.

As for the comments about not returning &mut, the other option is to remove and re-add the entry on every usage, which is far worse than searching the map twice. `get_mut()` is not evil. It exists for very good reasons.

I've been searching for that estimate but haven't found it. Do you have the source?

There was definitely an expanding bubble that looked exactly like a shock wave. I have no idea if there might be something else that it could be, but it looked like a shock wave to me.