631–640 of 772 posts
It keeps track of which space is allocated by logging every allocation and deallocation. When initializing an allocator, which can be implemented in any way, this log is replayed.
If the map becomes too big it is rewritten so it is equivalent to the old map but with no redundant entries.
You can evaluate infinite rules, with automatic incremental updates (no re-evaluation if not necessary), with O(1) time complexity. The tradeoff being that you have to hold a very large graph which represents your rule set in memory.
The union-find data structure / algorithm is useful and a lot of fun. The goal is a data structure where you can perform operations like "a and b are in the same set", "b and c are in the same set" and then get answers to questions like "are a and c in the same set?" (yes, in this example.) The implementation starts out pretty obvious - a tree where every element either points at itself or some thing it was merged wi…
Basically they managed to replace a full-fledged graph database with small piece of code using union-find in Go. Was a great talk.
https://skillsmatter.com/skillscasts/8355-london-go-usergrou...
"This is the story of a clever trick that's been around for at least 35 years, in which array values can be left uninitialized and then read during normal operations, yet the code behaves correctly no matter what garbage is sitting in the array. Like the best programming tricks, this one is the right tool for the job in certain situations. The sleaziness of uninitialized data access is offset by performance improveme…
That's the perfect word for this kind of thing. It's not wrong, but it's sleazy alright.
Earlier quoted context omitted.
I wonder if Swift's AsyncAwait could be used in such a way.
Sure it's possible, we need to await for the Task if it already exists on the dictionary, for example we could imagine writing something like this inside an actor to make it threadSafe. private var tasksDictionary: Dictionary > func getData(at urlString: String) async throws -> Data { if let currentTask = tasksDictionary[urlString] { return await currentTask.value } let currentTask = Task { return try await URLSessio…
Not a very deep CS-y one, but still one of my favourite data structures: Promise Maps. It only works in languages where promises/futures/tasks are a first-class citizen. Eg JavaScript. When caching the result of an expensive computation or a network call, don't actually cache the result, but cache the promise that awaits the result. Ie don't make a Map but a Map > This way, if a new, uncached key gets requested twice…
Earlier quoted context omitted.
I have written many tools that do something like this, very useful. Just gotta be careful with memory leaks, so (for a TS example) you might want to do something like this: const promiseMap > = new Map(); async function keyedDebounce (key: string, fn: () => R) { const existingPromise = promiseMap.get(key); if (existingPromise) return existingPromise; const promise = new Promise(async (resolve) => { const result = awa…
Won’t JS garbage collect orphaned references? Why is this necessary?
OP is intentionally caching results of, presumably, expensive computations or network calls. It's a cache. There is no memory leak. OP just did not detail how cache invalidation/replacement happens. The 2nd comment adds a rather rudimentary mechanism of removing items from cache as soon as they are ready. You get the benefit of batching requests that occur before the resolve, but you get the downside of requests coming in right after the resolve hitting the expensive process again. Requests don't neatly line up at the door and stop coming in as soon as your database query returns.
Typically you would use an LRU mechanism. All caches (memcached, redis, etc.) have a memory limit (whether fixed or unbounded, i.e. all RAM) and a cache replacement policy.
Input, Output Unionnions. basically a input struct into a algorith, layed out in such a way, that the algorithms output, always only overwrites input no longer needed. If done well, this allows for hot-loops that basically go over one array for read & write-backs. After all, its all just memory and to use what you got in situ is the fastet way one can go. No pointers to dereference and wait, just the input, computate…
Cache-Oblivious Data Structures: https://cs.au.dk/~gerth/MassiveData02/notes/demaine.pdf A vaguely related notion is that naive analysis of big-O complexity in typical CS texts ignores over the increasing latency/cost of data access as the data size grows. This can't be ignored, no matter how much we would like to hand-wave it away, because physics gets in the way. A way to think about it is that a CPU core is like a…
Latency Numbers Everyone Should Know https://static.googleusercontent.com/media/sre.google/en//st...