Comparing algorithm costs

If you want criteria to choose directory structure, AFAIK usual approach is to take relevant benchmarks, code alternatives and test performance. The result may be something like "if less than 50 entries, then use linear search, otherwise use a search tree". AVL trees and similar approximately balanced search trees offer you upper bound on number of memory accesses which is similar to average. And this upper bound is explicit. Depending on point of view such trees give you warranty of modest access time (optimist point of view) or warranty that your access time will be close to worst case (pessimist point of view). As you noted, in system with cache upper bound gets much higher due to possible cache misses. Still, this upper bound is likely to be much lower than upper bound for linear search or for a hash table.

AVL trees are considered "in memory" data structure, you could try to use them in different setting, but this is non-standard use so do not expect much help from texts (or form other folks). For use on block media variants of B-trees are preferable (more modern variants are considered significantly better than orignal B-trees).

Various approximately balanced trees offer similar average performance. In many cases performance differences between them do not matter. If you care about differences, then you need to do your own measurements. In fact, binary trees without balancing have average search length only some tens of percents longer than approximately balanced trees, so without measurement it is hard to say if approximately balanced trees will give you better average performance than simple binary trees (of course without balancing worst case bound is gone).

Long ago I used (a little) OS/360. It gave you a lot of choices for "access methods" and various parameters. For users it was a pain to specify all that info and AFAIK frequently led to suboptimal performance. AFAIK it was rather common experience that various user controlled tuning parameters may be good for really stupid software, but usualy program has more info (due to statistics from past use) than users, so can better tune parameters.

Concerning directories in convential OS note that users are much slower than computer. So user-created directories by necessity will be quasi static with infrequent access. So other aspects will not matter much. Things may be different for directories used by a program, but OS interaction tends to be much heavier than purely user-space things, so normal programs are unlikely to make very heavy use of directories. Of course, heavy use may arise if programmer did not think about consequences of say user actions or configuration settings. But if programmer did not predict correctly directory use, would you trust him/her to correctly give you information about characteristis of usage?

I inherited a website. It has a single "data" directory which as of today contains 108771 files. This is on traditional Linux filesystem that AFAIK uses linear search to find directory entry. Yet the website works. Performance is rather unimpressive (about

Theoretical setup for large family of search trees is that you have otherwise arbitrary keys which you can compare. Since nature of keys is not specified, the best you can do is to compare number of comparisons. If you have extra information, you can use it. But densly packed unique integers as keys are really different thing. Already, say 256-bit integers as keys (for example they may be SHA-256 hashes of something) are really not much simpler than arbitray keys.

Well, for my non-filesystem purposes I looked at string storage. My conclusion was that for _my_ purpose hash table was the best. Basically, each tree node needs extra space for pointers. That nullifies most if not all savings due to sharing some characters in the keys. I store keys in aligned way, null padded to whole words. That way I can use word operations for comparison and hashing. Average number of trials per hash table access is low enough to make a difference compared to a tree. And IME hash table is slightly simpler to implement (I implemented AVL tree, did not try more fancy kinds of trees).

I would probably _not_ use hash table for filesystem case. In fact, I would probably start with linear search and look for alternatives only if I had evidence that linear search is inadequate for my use.

You rebalance AVL tree only on insertion or removal, each of them performs equvalent of a search as part of its work. When inserting you need at most one rebalancing step, when deleting you may have multiple rebalancing steps, but average tend to be low.

A guy wanted to optimize access to record fields in a compiler. Originally that was linear search on a list. The guy wrote code that sorted the fields and created table for binary search. Then he did measurements which indicated that above

This is well-known approach. It is for you to decide if you need something like this. And if you do, it is for you to do measurements. Similar things may appear as excercises in various books, but no text will spend a lot of time on this: basic idea is obvious once you heard it once, details depend too much on specific problem.

For me answer is "essentially never", I do not have '\Windows' on my machine. I can not access '\Users\Me' as there is no such thing on my machine. If you ask about "system directories" on my machine, programs access them to read configuration files and load shared libraries. And some things are accessible only to programs having appropriate priviledges. As you probably know part of OS interface is via fake filesystem.

I mean that there is general knowlege and there are specific situations. People can provide you with general knowlege and possibly with specific information about situations they met. You ask as if you thougt that issues specific to your problem are part of general knowlege. AFAICS they are not.

Effects of media are considerd via access time, that covers discs and reading from flash. Flash did not exist when classic texts were written, so they do not discuss it. Some newer texts mention flash.

Concerning distribution of keys, classic analysis uses uniform distribution. In systems with caches this is worst case, any other distribution tend to more or less prefer some location which tends to increase cache hits. Some data structures explicitely try to take advantage of nonuniform distribution. OTOH if you did excercises say in my copy of Tanenbaum "Computer architecture" you will see that with good data structure distribution must be very nonuniform to give you advantage (that is trying to "optimize" data structure for nonuniform use actually may loose).

A lot of folks write single-threaded applications. I never programmed a Mac, but I heard Mac programeres repeating basic mantra "you can call GUI operations only from GUI thread". AFAIK several major commercial packages are mostly single threaded. Only small performace critical part is multithreaded. Usually a machine runs a lot of things. OS is supposed to give illusion that a program has dedicated access to the machine. Which may work well enough or not. But if other things have negative impact, then program my be given dedicated machine. So assuming dedicated machine in many cases works well enough.

On slightly deeper level, if you want to spread computations onto multiple machines, then you face new issues. If those issues overlap enough with algorithmic issues, then you enter domain of parallel algorithms. But it makes no sense to study _all_ algorithms as parallel ones: same present troubles so that currently it makes no sense to spread algorithm work onto multiple threads/machines. In other cases trivial approach, that is running multiple independent copies gives all what is needed.

In slightly different spirit, small MCU-s are now cheap enough that you can dedicate one to various time critical tasks. I know that you decided to take different direction, but one can go quite far by using per-task CPU-s with modest amount of communication (so not in vacuum, but not far from independent).

That is what Minix did. Also Wirth in eighties advocated single thread for whole software stack (OS and applications). Works reasonably well in many cases, but there were serious drawbacks. Wirth approach lives up to now and has some fans, but instead of being a standalone OS it is now just a single single-threaded program running under conventional OS.

My impression is that Linux uses per directory locks.

Issues of this sort have a lot of commonalities between themselves and loose connection with algorithms. So they are considered a separate subject.

If other things have more need of cache, they are presumably more important and it does not matter that they evict (part of) your tree. The point is that under random access frequency of access decays pretty fast as you go down the tree. That is enough to understand interaction of the tree with the cache.

Well, atomic operation by definition is not interruptable, so in correct system it is _not_ interrupted. Concerning trees on disc: main issue is access to blocks and that is taken into account in algorithms from B-tree family. AVL trees do not address this concern.

Well, by paging above I understand having virtual memory bigger than physical RAM and implied by this exchange of data with backing store.

Sure, you can use paging hardware for various puropses. You need to look at page fauls and TLB misses. If handling of them takes only little time (which AFAICS is a frequent case), then there is no reason to think about it. If it takes so much time that this matter, then you are back to paging friendly data structures.

I did that. I hacked one of my BSD boxes to log lookup, create and unlink operations for a few days. Then, used those to drive the creation of various dictionary structures.

The results were useless -- because one doesn't resolve "names" very often on a desktop/server computer. Because the only named entities are coarse objects (files, directories, pipes, etc.).

There would be a flurry of activity when a program was started (as the .so's were resolved) and then nothing as the programs just did their thing.

My system is more decomposed so more compartmentalization is possible. When a task (process) is created, its parent builds a namespace for its use. These names are local to THAT child process. And, represent the sum total of everything accessible to it!

So, there is no "/etc/passwd" or "/dev/ada0" or any other named entity you would likely encounter in a legacy system. Even stdin/out/err are gone, replaced by a handle to this namespace and a set of permissions that its parent has given it to access/manipulate that namespace.

So, to emulate a legacy "filter" application, the first thing it would do is resolve "stdin", "stdout" and "stderr" (assuming it had conspired with its parent to name those thusly). If it tries to resolve "StDiN" it will fault -- the equivalent of a compile time linkage editor error (because the label "StDiN" does not exist)

A malicious actor trying to resolve "/etc/passwd" will similarly fault (because its namespace would not contain such a binding unless it was intended to access that object!). There's no need to return an error to the program as it is defective and *should* abend.

As a result, it is not uncommon for a program to have to resolve lots of objects before it is ready to run. And, thereafter, to continue to create/resolve objects as directed by its clients.

If you watch the filesystem interface (where identifiers are created, deleted and resolved) on a typical program, there isn't much going on after the program starts up. So, instrumenting a legacy application isn't very instructive.

You don't want to expect an upper bound. You want to expect a bound that represents the "best case" for your particular usage pattern. And, select an implementation that best fits that pattern.

E.g., if you wanted to emulate a legacy interface, you'd likely have a NameSpace that looks like: /standard file descriptors /stdin /stdout /stderr /other objects I need /stuff that I create If you adopt a policy that mimics the startup code in a legacy system and explicitly resolve stdin/out/err early in main(), then you can delete the "/standard file descriptors" Context from the NameSpace and free up those resources.

If the program's job is to create TCP connections for its clients, it will likely continually be adding and deleting entries from the "/stuff that I create" Context. But, these can have arbitrary names (0x01, 0x02, 0x03, 0x04...) as they likely have no specific significance. When client X asks you to set up a connection to some host, you bind that connection to an unused identifier under "/stuff that I create" and pass that object back to the client.

When the client invokes the close() method on the object you passed to him, you close that connection and decide if you want to cache the now unused identifier (in teh expectation that someone will ask to have another connection created) or delete it based on your own design policy.

Think about how many "things" are created, accessed and destroyed in a machine as it runs. Give each of them an identifier so that the entity that created them can manipulate them and pass them to clients. Instead of an "address" that exposes the object's internals.

If you know the structure is not likely to be altered, then there is nothing wrong with storing it in a "less durable" medium. YOU should have that choice -- not the OS. (and you shouldn't have to write your own routines to implement a dictionary)

If you start having to deal with sharable structures, the performance hits between coarse locking and fine grained locking are factors of 10 (as the size of the tree grows)! If you add this to an implementation selection that favors a particular usage style, the differences are well worth the complexity.

But, this requires an intimate understanding of your algorithm's design and performance along with the "hints" you can provide to the Context's constructor.

If, for example, you treat the Context as just a "list", then you aren't really interested in sorting it but, rather, accessing the "next" key. Insert, lookup and delete can then be simple operations: insert(x) list := x :: list delete() list := tl list lookup() list := tl list; return x And, sharing this just adds a fixed cost to each operation regardless of list length.

I assume developers are "skilled in the art". But, at the same time, expect them to make mistakes in implementation. As long as their "mistake" gives them the desired result, it's tolerable.

That's the point of the exercise I attempted, above. The "namespace" in a conventional system handles just coarse objects that are infrequently referenced. You neither PAY for the cost of its creation nor incur much total cost for its use (until you access something that you shouldn't)!

That's not the case where every operation is via a capability and those capabilities are provided via named dictionary entries.

What timeliness guarantees does the server have to meet? And, for how many concurrent clients?

I can multiply using repeated addition and still get the same result as invoking a multiplicative operator. If I don't care how fast the program runs or how much it impacts others (including its clients), why not?

Number of comparisons and amount of work required to maintain the dictionary structure in the face of alterations (add/delete/rename). But, only the entity USING the dictionary -- HIS dictionary -- knows how he will use it.

Why are they inferior to any other identifier for objects whose "name" is not of interest beyond as a reference? We use memory addresses to reference structures all the time -- do you care what the actual address is?

But, memory addresses refer to entities on YOUR host. How do you reference something on *another* host?

Depending on how long the strings are, how many and how "static", you can create a variety of different techniques for storing "string dictionaries". Tagged files are a common approach if the total amount of storage is reasonably small -- if a string shrinks, just pad it with NULs. If it needs to grow beyond the length of any adjacent NULs, then you effectively garbage collect and move everything that follows "down" a bit.

When you run out of space, the operation is "not permitted".

Averages only matter to folks writing textbooks. YOU know what you need for THIS algorithm (as contrasted to THAT algorithm). Pick the implementation that will give you the best performance for YOUR needs.

But that decision simply relies on size/quantity. If your access pattern suggested a LIFO or FIFO, both would be bad choices. If you had to call on an existing service to perform this action on your behalf, you would want that selection to take into account these issues. The goal of an OS is to provide services that an application will likely need (much the way that stdin/out/err are magically handled FOR you).

With a namespace per process, you can guarantee that a particular process can't access anything that it isn't intended to access. You don't need to layer ACLs on top of a filesystem interface.

I can give a program a handle to "garage door" and embed ONLY the abilities to determine if it is open/closed, and CLOSE it (exactly once). It's job being to make sure the garage door is closed at sundown.

And, I don't have to worry about it accidentally (or maliciously!) opening the door. Or, adjusting the temperature inside the house.

Because, if I had built a discrete device to close the garage door at sundown, I would never think of giving it access to the thermostat!

The idea to instrument the filesystem came from a colleague. Letting a "typical computer" generate references to the namespace (of that computer) and just logging them as "test data" to evaluate with my dictionary algorithms.

While conceptually equivalent, it fails as I described, above.

Another approach is to categorize the pathological conditions for each algorithm choice and decide if a "bad hint" would cost a program more than the good hint might provide. (I.e., assume developers aren't good at hinting).

These don't require specific knowledge of an application beyond the fact that a dictionary is involved.

Disks, drums, tape all were access time and pattern (SASD vs. DASD) and capacity. Note all the work done on tape sorting algorithms...

And they run on multithreaded machines. Because the OS DESIGNER has insulated them from these issues with the mechanisms he offers!

!!

I've done that in the past. But, they were tightly coupled so there was very little overhead in delegating a responsibility. This is now common with GPUs, NICs, etc.

The cost of a tiny MCU on the end of a long wire, powered BY said wire (because you don't want to have wall-warts all over the place and deal with that reliability issue) has a floor that makes the difference between a "PIC" and a multicore SoC pretty insignificant (when you consider all of the costs of dumbing down the motes).

Putting "enough" smarts at each node makes it easier to scale an application. I have about 30 cameras in my current system. How big of a computer would I need to process all of that video concurrently? When I add a 31st, will I have to replace/upgrade that computer?

The equivalent in AVL trees is fine grained locking. As mentioned above, the performance improvement is quite significant. ("Make no change unless you get at least a two-fold increase in performance")

But they aren't. It's important to understand where algorithms expect atomic operations -- especially when its a "macro" operation (like a tree rotation).

This particularly as people increasingly use HLLs. Is this safe? long result = 123456L; On which machines??

But the system only knows something must be atomic because the developer TOLD it. So, the developer has to know which operations need to be treated as such. (see above)

Again, with HLLs, the cost of implementing an atomic region is usually expensive. Making them even more "critical".

I have no backing store. Yet, use paging extensively.

E.g., I have a daemon that cycles through every physical page of memory, copies its contents to another page, maps that page into the appropriate page frame(s), and then exercises the isolated page to determine how reliable it is.

Without paging, anything that I wanted to isolate would have to be indirectly referenced (e.g., pointers to objects and accesses all done relative to those pointers). With a low probability of getting that right (what if a stale pointer exists and is used after you've "moved" the page out of the way?)

My fork/exec relies on CoW semantics to speed up and simplify the operation (why copy an entire process if the child is only going to use a portion of it?)

I use paging/VMM to implement DSM. And, call-by-value semantics for function calls.

I use the MMU to protect objects from actors, code from data, etc.

Hashing is fun.

John Larkin Highland Tech Glen Canyon Design Center Lunatic Fringe Electronics

Look-up tables.

Linear searching can get tedious.

John Larkin Highland Tech Glen Canyon Design Center Lunatic Fringe Electronics

On 04/20/2026 08:15 PM, john larkin wrote:

It's a start.

Kind of like free-lists, it's a usual first option that somehow never is in the algorithms & data structures book.

The economies that make the scales in terms of the budgets in the systems, in the embedded world is still theoretically on the order of the thousands, vis-a-vis the billions, though since megahertz and gigahertz chips are thousandths the cost of a few decades ago, the economies that make the scale sometimes have inverted since the usual applications were first realized.

Then, for something like memory, since the computer is going to keep track of pages up above bytes, having it so that any sort of container on the heap works on allocations a page at a time, may make sense to work the linear in that, vis-a-vis, the log, or log base two lg, of the usual account of the binary tree, then often enough the hash table, or dictionary, the associative array. Then the "constant time cost" of that as linear, for example can be both "before" and "after" the usual tree-traversal, where in the usual examples it's "after", then called "constant-time", since the size of the constant of the linear section is << smaller than the log sections.

Using the standard library like STL or boost or "the standard containers" of course is a good idea when looking for options to match the algorithm to the data structure.

Then another thing that can make sense is to project a lot of if/then statements into a great amount of space, then to use the super-scalar the bit-wise, for example when there are lots of rules, instead of just iterating over those, making them in large words, and making a block that makes the matching words from the items, paying the cost to compute the words, then that matching is binary operations. This can reduce a factorial to a sub-factorial, for example, so, gaining several orders of the linear.

About search and predicates, everybody knows yes or no, if/else. Then, a usual idea here is called "yes/no/maybe" or "sure/no/yes". So what it is is there's a bunch of search conditions. These are to be combined, and furthermore just added and removed or sent over the network, "filter conditions" say for a "data table" or along these lines. Then, some of the items to be filtered are marked "sure" then there are the negations "no" and then what remains "yes", for sure/no/yes a.k.a. yes/no/maybe. Then the conditions of the predicates are usually enough > < ! ~ and these kinds of things, "in" and so on, "equals", the predicates are of these kinds of conditions. Then, also multiple controls affect these, so the "filter predicates" to make a filter predicate overall, get composed this way. Then for ranges or "between" is that that's two filter predicates. So anyways then the maintenance of the filters is just adding and removing those, then furthermore it's the same set of predicate conditions client-side or server-side, so the predicates can be sent to something like "search" to return filtered output, these kinds of things. So, any kind of table to be filtered be these things mostly comes from the frameworks these days, these being one of the parts that's not included. Then usually enough also people want to see them "in English" vis-a-vis "the search syntax", by making a closed world of conditions, then according to the operators then the textual, numeric, and calendric data, has those bracketed out in the routine, then they can be composed. The filter predicate is invoked all the time so it makes sense also that changing it costs about zero.

About the branch-free and lock-free, the usual idea with computing binary words is making branch-free the matching, by using look-up tables to result that the binary arithmetic results producing indicators bit-wise what would be the results of the evaluating the predicates. Then, evaluating those is still predicates, yet, it's bits. Also then that can be lock-free in the sense of lock-step, massive wide parallel.

Then, another idea is about the partitioning and as data grows over time. So, data grows over time, and then a usual enough idea is that it goes in the partition bucket. So, an idea of pyramidal hierarchical search, through the tree of these, is that as the partition gets topped off, alongside it are generated the bit-wise words making the stamps of the indicator bits of the contents. Then, when looking for matches, the layers get peeled off or traversed, while the bits are still lit. This way an arbitrary large amount of partitions is rapidly pared for rare, or specific, search terms.

"Lock is lit."

Another example of greatest-hits is the index-file, or index-offset file, a most usual sort of idea that when there are a bunch of offsets in the linear, where those would be in the ordinal, is for making an index of the offsets, which is fine as long as the file never changes, otherwise that as a "cache" of sorts its invalidation then sees re-build.

The use-case here is "a file-system tree its storage and search", exact match, then usually enough the idea is that any given search has no common terms in the path with the previous search, yet, often enough it all goes to the same place. Then, a usual idea of a "cursor", after a "cache", is a handle, with a usual enough idea that caches get invalidated and cursors stay alive. Then if a process has a file-system cursor, that's usually in the context of file-tree-walk, about where often enough file-system operations live behind syscalls, vis-a-vis a tree, and about separating traversals and direct accesses.

A "handle" is a usual sort of idea, usually enough any sort of not-unbounded resource with reserve/release semantics. The "atom" is usually enough handles, for example for "the string atom", or "interned strings" sometimes they're called, then for example the usual idea of an "adapter" its instances are handles, then for example having their own cursors, also handles, and so on. These are the handles.

So, caches, basically are as of the idea of "key-value stores". Then, whether those can preserve index offsets, for example path-traversal paths, is about where the path is a traversal, or a value. These are as like entry-points to the data structure, vis-a-vis, entry points to routine. So for something like a filesystem, there are paths, usually enough about absolute and relative paths, and resolving paths.

Then, a handle, to path traversal, is often enough going to have one of two modes on each branch of the path. It either changes or stays the same. Then a usual idea of keeping both MRU and LRU caches that are small for small linear constant, and that the automatic maintenance just either always increments the hit or always rotates the hits, otherwise being a miss, reflect either way the mode stays the same or changes, results free hits when there happens to be a mode.

About path again, then usually enough the file-systems don't have much in the way of meta-data after stat, about things like my favorite tool "find", vis-a-vis file-tree-walk and metadata. So anyways at some point there was XPath, for XML toolchain, that was probably around for decades before XPath saw the light of day, which was around decades before jsonpath became a thing, point being that the specification of the path traversal is a value, vis-a-vis, the actual offsets to be navigated being surfaced above the adapter/syscall and being a value.

FS: file-system DB: data-base MQ: message-queue WS: "web-service", anything else

"Look-ups" then "fall-backs" isn't an un-usual idea. A tree usually enough has about the same amount of nodes on each branch, about limits like PATH_MAX and FILENAME_MAX (NAME_MAX). DIRENT_MAX wide? DEPTH_MAX deep?

So, usually filenames are "ergodic" or have "high cardinality", while the roots of the tree are usually enough enumerable, about making atoms/interns of the path roots, and then, often there are only so many "file extensions", and they're very usual in filesystem layout conventions, for example about making atoms/interns of file extensions. So, one idea is to make the roots distinguished and make the leaves distinguished, then that all in the middle is paths.

Then there's symlinks, ..., usually enough considered outside the convention or transparent to the convention.

The way chroot works is one thing, vis-a-vis, virts, that all being buried and opaque to the usual runtime.

It's interesting to consider all the levers and layers and cases.

"Whatever works will get used up" is a usual enough idea. ("Jevons".)

Running '70's-style operating systems on 2020 hypervisor-virts, makes for an idea to write "many-core native" the system vis-a-vis ideas like "cloud native" the applications and this kind of thing.

POSIX is considered a great and useful compatibility layer.

These days there might be a suggestion to give each application its own copy of "shared libraries" since they're modifiable.

Making limits then that a given amount fits in a box, for example that aligned to pages, then having so many given boxes, and that aligned to partitions, usually enough makes for "a tree of trees, partitioned", vis-a-vis, for example, symlinks and cycles.

Trees: alike directed a-cyclic graphs.

Directed and un-directed trees (or with links and/or backlinks) are to be disambiguated. Here they're generally considered directed. This is where _Harari_ graphs are usually considered directed, and _Berge_ graphs are usually considered un-directed, bi-directional, the direction of the arrows of the vertices connecting the nodes. Then, filesystem traversals are most often "down", yet resolving relative paths is a usual exercise.

Then, a sort of idea of "look-up fall-back" or "LUFB tree" starts to emerge, with a sort of idea that creation and deletion of files (or, "link" and "unlink") has its orders (of magnitudes of frequency and size), and then file modification (reads/writes) has its orders, with regards to frequency and size.

Then, a usual idea after bit-flags (assigning distinct individuals a natural number and thusly presence/indicator by that given bit in a machine-word/extended-word) and look-ups (ordinal offset to value-type, or the reverse of bit-flag indicators), then two things that come to mind are "Huffman coding", and, "arithmetic coding", when the idea that individuals have themselves different frequencies, then usually about the "prefix-property", and Huffman codes, or, "prime-assignment", and Huffman codes. I.e., in an un-interpreted bit-stream, it makes sense to have Huffman codes using the prefix-property so they can be distinguished and picked off the stream, while, besides bit-flags, then another idea is that Huffman codes are ordered from most- to least-likely, then to basically assign them to the n'th prime the n'th Huffman code.

What happens here is that there are "algebraizations", then to the "arithmetizations", and "geometrizations". So, then that's usually enough about operators and predicates, or as like functions: T -> T and functions: T -> bool. So, for example, then functions: T -> bit-offset or functions: T -> Huffman code, and their inverses being unique, or not, about functions and bi-functions and predicates and bi-predicates or functions: T, T -> T and the like, among bi-functions as like 2-ary-functions, then a usual idea is to assigned the frequencies as to make Huffman codes of things, or as to make arithmetic/geometric codes of things, then that for things like "operator overloading" that the "operators" (or predicates, tests) are natural, the same as the algebra or arithmetic or geometry.

Then connecting those to "the machine operations" is the usual idea.

So, there's a general sort of account that all these are always in play, about a general sort of idea of putting these concepts together to make a generic sort of adaptive data-structure, then for something like the idea that "Huffman codes are optimal", something like "under various configurations LUFB-trees result as a model of Huffman codes".

I remember one time somebody asked something about "implement a multi-set". So, this is a usual enough idea, like a set of keys mapped to each a count, like map-counts or count-maps, histograms, among usual sorts data structures, an associative array, many people's only notion of data structure, "objects". So I mentioned, hey, you know about prime numbers and unique prime factorization, right. "Well, sure.". So, you give each member of the set a unique prime number, then you start with an empty set the integer 1, then to insert items into the multi-set you just multiply it in, to test for presence test for divisibility, to remove an instance divide it out.

And he was like "wow, that works, and I never even heard of it before."

Most everybody's heard of "Huffman codes" and "arithmetic codes" though, it's a usual account of things like priority maps and algebraizations, arithmetizations, and geometrizations, then eventually for machine arithmetic, in machine architecture.

The devil is always in the detail depending on what assumptions you can make about the material being indexed and if it has a natural ordering.

Binary chop search can often be very effective - especially if the dictionary is not case sensitive and is amenable to pre binning on the first couple of characters with 26^2 possible entries in A-Z (even less if you reduce the possibilities to actual dictionary words).

The program Dasher is a rather beautiful example of a very fast way of inputting text based prose using around 1 bit per character.

I can imagine that caching and - worse - virtual memory would influence the design of stashing and searching. Some presumably efficient structures and search algorithms could thrash themselves silly.

Virtual memory is evil.

John Larkin Highland Tech Glen Canyon Design Center Lunatic Fringe Electronics

I remember one time I was looking around the database, and I noticed in the ALL_TABLES table or ALL_INDICES that the indices had a "type" column, and so, there are at least two types, "BTREE" ("NORMAL") and "BITMAP".

The BITMAP type index is used in applications like in the data warehouse applications, with for example something like a star-schema and "item" and "data" tables or "dimension" and "fact" tables. The idea is that when there are lots of concurrent queries, it's easier to just AND them all together. Seeing queries in these where the query is the outer product seems usually profoundly un-specific, yet, that involves the query-optimizer in the explain-plan.

So, there are lots of different workloads.

One time I added to libtiff basically sorting a list in what was a linear subroutine and after "qsort" using "bsearch", ...., though there were only half a dozen entries in the list. Was it worth it? (C doesn't have a standard associative array.)

So, there are cases for "low cardinality" and "high concurrency" and "low complexity" and "small constant", where it can make sense to organize either way,

I remember that these things are involved, then later they can be recalled instead of relearned.

Hashes can be a great idea, an approach to providing constant-size values often enough machine integers that have the property of being computable for any size object and being uniformly distributed over those, thus that as keys in a binary tree it results a more-or-less balanced b-tree. (Vis-a-vis "quad-trees" and "oc-trees" and the like, there are a variety of approaches to these since the '80's.) Then, the "stamp" is another sort of idea, basically to compute a "stamp" for a value like a string, for example, for the contents of the string like the character classes according to regular expressions, or particulars about "special characters", so that a "stamp" of a string basically indicates the presence or absence of character classes in the string. It's readily computed then for example whether a string contains a special character or a restricted alphabet is computable, then that it may make sense for it to be "memo-ized", remembered, and that access patterns protect that modifications to the string variously do or don't invalidate the stamp, similarly to how hashes can be memo-ized.

If premature optimization is the root of all evil, is the root of all live premature optimization?

A few months ago or so I posted here an outline of operating system design, or about allocation strategy, idea being to only ever allocate a page at a time and then have the user do their own defragmentation of the page their addresses in it, then that the operating system can use "virtual memory" (indirection/abstraction of offsets) to make that transparent to the user, while making it so that workloads that often are allocating/deallocating basically thrash on their own page instead of making the operating system do it ("Critix", 3/28-3/29).

The, "content addressable memory", is a data structure often in silico that provides un-intuitive, or, "against the grain", sorts of results.

This is exactly the problem: in general, an OS can't make ANY assumptions about the keys OR the operations (and ordering) performed on the dataset.

OTOH, the developer knows how *his* code will access them. So, he should provide suitable hints to the constructor (which his PARENT invokes prior to his coming into being).

Existing namespaces (i.e., The Filesystem) are overly large (how many entries does a program typically reference BY NAME?). Adding and unlinking entries is relatively costly -- unless a very large disk cache exists AND HAS BEEN POPULATED. They are organized with no clear preference towards an access pattern. And, because they are global structures (we all know NOT to unnecessarily share data in a program!), they rely on additional measures to protect against unintended access.

As a result, programs are developed that can't leverage that namespace to their advantage. (And, there are no guarantees that any efforts to attempt to do so will yield rewards). To abuse a cliche: It tries to be NOTHING to NOONE.

Imagine how you would structure an application if the language only supported lists. Or arrays. And, how a naive developer could fail to understand HOW each of those were supported and chose to access them in the most pathological order possible!

Imagine a process generates "timeclock" data for your employees. Another prints paychecks. The data exchanged via a dictionary. Why would the former bother to order the keys in the dictionary? Wouldn't FIFO ordering be more appropriate? (and, inherently fairer; if Mr Zed's data was available early, why should he have to wait for everyone else's paychecks to be processed?)

The typical interview question that catches most newbies -- failing to enquire as to the nature of the dataset BEFORE picking a sort algorithm on which to demonstrate their coding ability. (ANYONE can wrote code. Knowing what to write is the modeling question at the heart of software design)

Because the tool knows how it will be used! It would be folly to use it to generate entropy... :>

Such generalizations assume "random" add/delete/search queries. This might make sense on a shared global data structure as you don't know which actors to favor in its design.

Many commonly used devices have a notion of "favorites" -- whether desktop shortcuts, MRU files, etc. BECAUSE PEOPLE DON'T WANT TO WASTE TIME LOOKING THROUGH A LARGE DATA STRUCTURE (for something they know they will likely be using soon/often).

But, these are consequences of that data structure not giving preference to THEIR usage patterns. "Let's invent ANOTHER mechanism to layer on top of this first mechanism (instead of rethinking the whole problem)..."

War story: Speaking of dirty fingernails, I have an example from the latter half of the 1970s, when computers were expensive and slow. I was programming a midi-computer (a SEL 32/55, few relay racks in size) that drove a display showing radio emitters situated around a (simulated) aircraft shown on a map of local terrain. The map and emitters moved steadily from top to bottom as they would as seen from a flying aircraft.

The maps were large, and lived one a new innovation, a washing-machine sized Winchester disk, with removable platter assembly (for which I also wrote the I/O driver).

The problem was that there wasn't time to get the next map tile off the disk before it came into view. Caching could not work because the cache would need to be larger than the washing-machine disk.

But we knew something important - the airplane usually flew steadily, so one could predict which tiles were coming and roughly when. So, we ordered the predicted next tile when handling the arrival of the tile that will be displayed next. If the airplane maneuvered, some tiles were read needlessly, but not enough to matter. This worked very well.

Joe

We did something similar in the design of an early MCU-based LORAN-C receiver. The software dynamically tracked the received radio signals from Master and two slave (X/Y/Z) stations. The "third rising zero-crossing in the pulse envelope" was the reference point (unless manually overriden). When, in time, it occurred was the significant measurement (and, it's relative positions to the other MXYZ signals) to determine position on lines of constant time-difference.

Of course, you are moving, at the time, so the times (absolute and relative) are changing, along the way.

Once the RF signal has "passed", there's nothing you can do about it but wait for the next one and hope you catch it properly.

So, we would note the effects of our motion wrt the different broadcasts and "anticipate" where the next zero crossing would occur for each of the received signals. This let us focus our "acquisition" resources in the region around the anticipated zero-crossing instead of having to listen to "dead air" between pulses.

Periodic processes are considerably easier to model as you have some expectations that you can factor into your expected observations.

E.g., a tablet press produces "event serieses" at ~200Hz. But, these aren't truly independant as there are mechanisms and geometries that are shared by all event serieses. E.g., event 100 shares the same mechanical constraints as event 200 -- though sharing less with event 101 or 199. And, 50's performance is closely related -- but different.

So you can feed data forwards and backwards to adjust your understanding of a particular event based on observations of other events that share some aspects of the mechanism/process with them. You can anticipate and respond proactively as events can't be replayed once they've occurred; figure out how to address ANTICIPATED shortcomings before they manifest.

Yeah, basically the same idea. It was of necessity common back in the day.

Joe

It's also good engineering. You want to develop a good model for the problem you are addressing. From that, you know what you can IGNORE as well as what you can RELY UPON.

If I suddenly saw the vessel "100 miles" (from where it was located a few seconds ago, then either my previous notion of its location was incorrect OR my current notion of its location is incorrect OR something is broken.

In either case, I have to take some sort of corrective action.

Don Y snipped-for-privacy@foo.invalid wrote: |----------------------------------------------------------------------------| |"We did something similar in the design of an early MCU-based LORAN-C | |receiver. The software dynamically tracked the received radio signals | |from Master and two slave (X/Y/Z) stations. The "third rising zero-crossing| |in the pulse envelope" was the reference point (unless manually overriden)."| |----------------------------------------------------------------------------|

A grant application for eLORAN has argued that eLORAN had made ships workers so reliant on not manually navigating and so reliant on not manually maneuvering, that maintaining eLORAN is a safety-critical duty. I suppose that eLORAN or a predecessor had been proposed to replace 'unsafe' manual operations with a 'safe' automatic process.

(I do not want to say "sailors" instead of "ships workers" as such ships do not actually use sails.) (S.