proposal

Sep 20, 2026 Last reply: 1 week ago 119 Replies

The *point* is there is a cost to walking such structures. Ideally, one wants constant time operations. Barring that, something like log N. If you have to walk a structure to *find* an entry, then this is at best linear time -- not counting the cost of the resources allocated and thereafter wasted.

For a news reader, you barely need *megabytes*. If you have opted to put gigabytes into a product, you likely *need* gigabytes (else you could reduce the product's cost by provisioning it with less resources)

If you don't have backing store, then running out of memory is a panic().

The operating system's role is to manage resources. How efficiently it can do that depends on the set(s) of applications running on it.

And, you reboot the processor and life goes on.

Most applications aren't "desktop" applications. The consequences of exhausting a resource can be significant -- up to and including loss of life.

Unless you can KNOW, a priori, what all of the allocation/release patterns are and GUARANTEE you won't run out of resources, you can't use a dubious algorithm in a situation where the consequences are more than "inconveniencing a user with a spurious reboot".

Simple only works for simple problems with dubious performance requirements. When you have to meet performance goals, you can't "fudge" your approach to a problem.

Imagine every filename on your disk being present in ONE long list so you had to walk that entire list to find the file you sought. Imagine how dreary the performance would be for ~500,000 files (most windows machines have comparable numbers of files).

So, you don't pick naive implementations just because they are "simpler".

Newsreaders are boring applications. No one sits and worries about how long it takes for an article to appear.

But, a DaVinci robot

formatting link
lethargic in responding to the surgeon's controls *likely* would have consequences. Or, the ABS in your vehicle. Or, even the responses of your

*mouse*/keyboard.

Being able to tailor an implementation to the needs of an application lets you match provisioning with requirements -- so you don't "pay" for resources you don't (or rarely) need... or, run out of resources unexpectedly. If an application wants a dictionary created that it will access using "small integers", you would create that (on demand) differently than one that wants to access thousands of entities using strings as keys (e.g., like in a filesystem).

Being able to create *both* types of dictionaries in the same deployed product is a win as neither has to be compromised by "settling" for an implementation that favors the other.

Do your coding right, and no =problem. Did you ever do any asm programming?

I am not talking abiut 'fudging', like yo udo in postings

I am toaking about coding..

Are you OK? Ever tried 'locate' on Linux Every so many hours all is scanfed and indexed and saved even on small systems I have a Toshiba 4 TB USB harddisc connected to this Raspberry Pi4 8GB, finding a file name takes seconds raspberrypi: ~ # df Filesystem 1K-blocks Used Available Use% Mounted on /dev/root 124334328 34040016 85195484 29% / devtmpfs 3879380 0 3879380 0% /dev tmpfs 4044244 12796 4031448 1% /dev/shm tmpfs 1617700 1344 1616356 1% /run tmpfs 5120 4 5116 1% /run/lock /dev/mmcblk0p1 258095 50413 207682 20% /boot tmpfs 808848 24 808824 1% /run/user/1000 /dev/sda2 3844420600 3538915572 110144364 97% /mnt/sda2 <-------------------------

The 4TB is almost full raspberrypi: ~ # locate NewsFleX.c /mnt/sda2/pantel/root/compile...20/pantel/NewsFleX/NewsFleX-1.5.7.1/NewsFleX.c /mnt/sda2/pantel/root/compile...20/pantel/NewsFleX/NewsFleX-1.5.7.2/NewsFleX.c /mnt/sda2/pantel/root/compile...20/pantel/NewsFleX/NewsFleX-1.5.7.3/NewsFleX.c /mnt/sda2/pantel/root/compile...20/pantel/NewsFleX/NewsFleX-1.5.7.4/NewsFleX.c /mnt/sda2/pantel/root/compile...20/pantel/NewsFleX/NewsFleX-1.5.7/NewsFleX.c /mnt/sda2/pantel/root/compile...20/pantel/NewsFleX/NewsFleX.c /mnt/sda2/pantel/root/compile...20/pantel/NewsFleX/NewsFleX.c~ /mnt/sda2/pantel/root/compile...20/pantel/newsflex/NewsFleX.c /mnt/sda2/pantel/root/compile/NewsFleX/NewsFleX-1.5.7.1/NewsFleX.c /mnt/sda2/pantel/root/compile/NewsFleX/NewsFleX-1.5.7.2/NewsFleX.c /mnt/sda2/pantel/root/compile/NewsFleX/NewsFleX-1.5.7.3/NewsFleX.c /mnt/sda2/pantel/root/compile/NewsFleX/NewsFleX-1.5.7/NewsFleX.c /mnt/sda2/pantel/root/compile/NewsFleX/NewsFleX.c /mnt/sda2/pantel/root/compile/NewsFleX/NewsFleX.c~ /mnt/sda2/pantel/root/compile/NewsFleX/slackware_32_bit/NewsFleX-1.5.7.1/NewsFleX.c /mnt/sda2/pantel/root/compile/NewsFleX/slackware_32_bit/NewsFleX-1.5.7.2/NewsFleX.c /mnt/sda2/pantel/root/compile/NewsFleX/slackware_32_bit/NewsFleX-1.5.7.3/NewsFleX.c /mnt/sda2/pantel/root/compile/NewsFleX/slackware_32_bit/NewsFleX-1.5.7.4/NewsFleX.c /mnt/sda2/pantel/root/compile/NewsFleX/slackware_32_bit/NewsFleX-1.5.7/NewsFleX.c /mnt/sda2/pantel/root/compile/NewsFleX/slackware_32_bit/NewsFleX.c /mnt/sda2/pantel/root/compile/pantel/NewsFleX/NewsFleX-1.5.7.1/NewsFleX.c /mnt/sda2/pantel/root/compile/pantel/NewsFleX/NewsFleX-1.5.7.2/NewsFleX.c /mnt/sda2/pantel/root/compile/pantel/NewsFleX/NewsFleX-1.5.7.3/NewsFleX.c /mnt/sda2/pantel/root/compile/pantel/NewsFleX/NewsFleX-1.5.7/NewsFleX.c /mnt/sda2/pantel/root/compile/pantel/NewsFleX/NewsFleX.c /mnt/sda2/pantel/root/compile/pantel/NewsFleX/NewsFleX.c~

Took 5 seconds The sda2 4TB harddisc did not even start up!

Beep!

Now Cuba imports sugar.

John Larkin Highland Tech Glen Canyon Design Center Lunatic Fringe Electronics

Lots of sharing is theft and poverty.

This is an electronics design group. What sorts of things do you design?

John Larkin Highland Tech Glen Canyon Design Center Lunatic Fringe Electronics

The United States has the highest number of Nobel laureates in the world, and many were born in other countries.

And the United States has 144 foreign-born billionaires. Lots of smart people come here.

It's cool, fun, beautiful, and a great place to design electronics.

John Larkin Highland Tech Glen Canyon Design Center Lunatic Fringe Electronics

Earth is doing fine with the population, but as people get fed and educated better (and play more video games) they want less kids. A gradual population decline sounds great to me. One billion would be good.

You are obsessed with Trump and with Larkin. That puts me in great company. Thanks.

John Larkin Highland Tech Glen Canyon Design Center Lunatic Fringe Electronics

Google larkin dremel

Nowadays, with AI, everyone is famous.

John Larkin Highland Tech Glen Canyon Design Center Lunatic Fringe Electronics

i4004, 8085, z80, 8x300, 68000, 32016

Because a database of each pathname was prebuilt and then simply scanned.

Add a file to your machine after the database was built and locate(1) won't find it.

The little USFF that runs my core network services (BIND, NTPd, xfs, bootp, etc.) has ~700k files on it (I build kernels there so it has the complete source for the system). This is comparable to the ~300K files and ~100K folders on this windows machine. I.e., there are about half a million named, unique entities on each machine.

[The silly notion of a single unified namespace forcing EVERY identifier to reside in this big arena]

If each file/folder name was a *single* character accompanied by a pointer to the next entry (i.e., a linked list), you'd need ~2.5MB to store that information (not counting the contents of the files).

And, on average, would have to examine 250K entries to find the entry you sought. Contrast this with a log N solution that requires ~20 compares. That's why a linked list sucks.

Now, try find / -name "NewsFleX,c*" -print which actually has to walk the filesystem structure on the medium (do it twice so you can benefit from cachine that data the first time through) and see how long THAT takes.

Operating systems use LOTS of dictionaries. Often, optimizing them for their specific uses and assumptions.

E.g., per-process file descriptors are stored in a simple array indexed by the (numeric) "file descriptor" -- because processes tend to open relatively few files concurrently (and a closed file descriptor can be reused for another file).

OTOH, the process table will reference 5 digit process identifiers -- but, there isn't a STATIC table capable of holding 64k process descriptors sitting around. Because the system likely can't support 64k active processes concurrently.

So, a *dictionary* maps a process identifier to a live (or zombie) process instance. This, a tacit acknowledgement of "holes" in the PID space which would make the same sort of indexed table approach used for fildes's impractical.

Active network connections, namespaces, etc. all rely on dictionaries to efficiently map keys to values. So, having an EFFICIENT way of creating these to suit differing usage and access criteria makes sense. A mechanism that doesn't "wait five seconds" to produce a result as these operations happen multiple times, behind the scenes, for every action that takes place in the system.

Coding each of those variants is a boring job well suited to an AI coder that can simply cobble the different approaches together into a unified, conditional implelmentation. And, summarize the break-even points for each implementation so the actual implementation of a specific dictionary can be optimized AT RUN TIME based on hints from the client requesting such a resource.

Because a process isn't as patient as a human thinking in terms of human-time.

Actually, the word is notorious. "Famous" implies positive connotations. Donald Trump thinks that he is famous, but he's just over-exposed.

If you can't even import spare parts for your sugar-cane processing machines, growing a lot of sugar-cane doesn't necessarily guarantee that you can extract enough sugar to satisfy your home market.

Sharing is theft? Are you on drugs?

I read this discussion in sci.math (which is one of the groups this discussion is crossposted to).

I like to design abstract art (though it's also fun to reproduce existing abstract artworks with math):

formatting link

Like I said. The Netherland has the Spinoza Prize (my wife was the first woman to win it) copied from the German Leibnitz Prize. Both were designed to stop America hiring away the best of the mid-career academics.

Some stay, but it isn't a great place to raise kids, even if you have pots of money.

With a whole lot of guns nuts who shoot loads of people from time to time. In fact gun owners mostly shoot themselves - the great benefit of making gun-ownership difficult is that suicidal people turn to less reliable ways of killing themselves.

Gun manufacturers in the US have clubbed together to spend money on propaganda that makes the right to own a gun and keep it at home a fundamental freedom. It's self-interested lying, but they make money of of it.

As for electronic design I was never all that impressed by the American stuff that our American customers insisted we used. Some of it was great, but a lot was very ordinary, put on the market before all the bugs had been cleaned out.

formatting link
Note a process may have "holes" in its fildes table if it closes a file and hasn't *yet* opened another that will reuse that fildes.

fd[012] (typ), of course, have symbolic names (stdin, stdout, stderr) and *likely* are always in use.

formatting link

Note that the PID is stored in the dictionary as (one of) its key; it is not *implied* by the OFFSET (index) into the table/array as was the case for fildes.

When you care about predictable performance (e.g., in cases where timeliness is a design and performance criteria), your choice of how a dictionary is implemented becomes significant.

Something, of which, "programmers" often are ignorant.

Authoritarian socialism tends to work that way. Democratic socialism, as practiced in northern Europe, leads to longer life expectancies than America offers, and it is noticeable that the poorest American state - Mississippi has noticeably lower life expectancies than more prosperous US states.

formatting link
Australia does better

formatting link
The Northern Territory, which isn't densely populated and has a lot of aboriginal Australians, does worse than the other states and territories (but nowhere near as badly as Mississippi). My youngest brother is a medical doctor and something of an expert on aboriginal health, and seems to think that they have cultural problems as well as low incomes. He started writing a Ph.D. thesis on the subject, but had access to a lot excellent of longditudinal (whole life-time) data and couldn't find the statistical tools that would have let him write it up in any particularly helpful way. Frustrating.,

John Larkin's sign-off line after any political rant.

It will find it after it has run uodatedb How often that runs is for you to decide

Why, just because you wanna be right? locate works for me instantanuous, and if I just ADD a file I also know where it is and if I wrote the code that 'added some file' I also know where it is.

Else wait for updatedb, or run it if you are in some hurry.

End of discussion,

Show us some code / some application you wrote, open-source it, something USEFUL or even some elctronics project. Else shut up with your ever *deverging* babble,

Beep Jippy IIA

It's a Constitutional right.

England hardly makes any electronic test gear any more. Nor does France.

John Larkin Highland Tech Glen Canyon Design Center Lunatic Fringe Electronics

So, if I want constnat performance from it, every time I creat() a file, I have to rerun it. Sounds awfully expensive when a better technique would eliminate that cost entirely.

No. Because you are refusing to understand the COST associated with walking a linked list.

And, as you only seem to think in terms of command line examples, that's the only way I can get you to SEE the cost of walking the entire structure.

Sorrym I am quite comfortable with my c*ck size. If you have some insecurity, I sugest you speak to a professional about yours.

"End of discussion. Programmer."

I can't see that. Google wants my life history first.

We collect numbers too. We digitize and analyze waveforms.

Sometimes we manufacture numbers too. We have random number generators in several of our products, and make many millions per second.

There are easy ways to make random numbers, but people tend to go overboard on them. I mean, if a series of numbers repeats every hundred years, not many customers will complain.

There have been many really bad ran() functions in computer languages. I fixed one in a fairly common computing language. The original repeated about every thousand calls.

There are electronic circuits that create interesting patterns.

formatting link

John Larkin Highland Tech Glen Canyon Design Center Lunatic Fringe Electronics

DT is wrecking your life. So am I, probably.

John Larkin Highland Tech Glen Canyon Design Center Lunatic Fringe Electronics

It was a badly drafted paragraph designed to support "well regulated" citizen militias.

If the gun manufacturers hadn't latched onto it as a way letting them sell a whole lot more guns to nervous citizen than was remotely sensible, it would have been amended into something safer (and more in keeping with the original intention).

That's what the EU is all about. Countries concentrate on what they do best. I worked for Eurotherm for a bit when they set up to grab the European market for cheap process control electronics. I proposed using a little bit of positive feedback to linearise a platinum resistance temperature sensor, but the guy who took over the project got nervous about the positive feedback. Honeywell later used the technique in their offering - it was a pretty obvious idea for a cheap correction.

Join the Discussion

Have something to add? Share your thoughts — no account required.

Didn't find your answer?

Ask the community — no account required