Comparing algorithm costs

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.

John Larkin snipped-for-privacy@Glen--Canyon.com wrote: |-------------------------| |"Virtual memory is evil."| |-------------------------|

Uh, but virtual memories became invented when persons used not have enough RAMs. (S.