What algorithm did Windows XP use to choose your initial user picture?(devblogs.microsoft.com) |
What algorithm did Windows XP use to choose your initial user picture?(devblogs.microsoft.com) |
A simple rand/mod based on first character of username should be sufficient?
But then it occurred to me that XP was of an era when you would absolutely spend an afternoon downloading some megapack of 10000 cool user icons.
If someone only gave me 2 minutes for this, because they think it is very simple (as always), I'd have done a count of files of a specific pattern in the directory and then picked a random index, very naive and quick and dirty programming, no sampling at all, just to avoid discussions why it takes so long with people who don't want to hear it.
This reminds me of when I did a lot of C#, Java, JS, Python in my life, filling maps of strings and objects until I started with zig and noticed how expensive and complicated strings and data structure allocations can be. It kind of blew my mind how much memory and computation we waste when we try to get stuff done as fast as possible because of budget/time constraints.
Its not like windows is the pinnacle of software craftsmanship.
Programming for MCUs. Less so today when multi-hundred MHz MCUs are cheap, but even several years ago there were a lot of products where you needed to use the cheapest MCU and everything it did had to be optimized to avoid stalls and edge cases.
Second is doing LeetCode problems for fun/practice. This will elicit a groan from a lot of people, but the algorithms and pathological edge cases you learn really do change your thinking. The most interesting ones are the hard problems where they’ve added some hidden test case that causes naive solutions and algorithms to blow up. You start thinking on high alert for edge cases and Big O problems. It’s more fun when you’re doing it to learn on your own than for forced interview prep.
Being tenured and one of the top engineers in your company with a very proven track record gives you quite a bit more freedom.
Why does Raymond assume counting the files is an O(n) operation?
Interestingly, when reading Raymond Chen's article I thought "reservoir sampling would compare the random number (between 1 and n) to 1, not to n, because that extends more easily to picking more than one element" - and that's what the actual Windows code uses.
OK, but isn't the kernel keeping the directory listing in the disk cache? Won't that prevent extra physical I/O if you do just read the directory twice?
If so, then in the second pass, it's all cache hits, and you're just paying the cost of calling into the file system. Hopefully that's pretty fast. But even if not, it's still absolutely dwarfed by the physical I/O required for the first pass. Windows XP era storage was spinning hard drives, not flash.
And if not, then I'm probably going to put my user icon coding task on the back burner and go ask the kernel team why a seemingly very common usage pattern isn't optimized.
(I realize he's not claiming the performance benefit was significant. I'm just trying to see it in the right perspective.)
selectRandomFromIteratorOptimized(iterator) { if (!iterator.moveNext()) { return null; }
var winner = iterator.current();
var count = 1;
while (true) {
var u = random_float_open(0.0, 1.0);
var skip = (int)Math.Floor(Math.Log(u) / Math.Log(1.0 - (1.0 / (count + 1))));
for (var i = 0; i < skip; ++i) {
if (!iterator.moveNext()) {
return winner;
}
++count;
}
if (!iterator.moveNext()) {
return winner;
}
++count;
winner = iterator.current();
}
}I don't know if they've relaxed this since the days of non-FPU CPUs - anyone know? If they let the Weather app use a webview, there must be some floating point usage in there.
This code is at a much higher level though - at the user shell level, explorer.exe.
Anyways, asking Google's AI to remove the above code's use of floating point results in code resembling the original version.
Trying to best Windows devs on performance becomes almost comical if you read the comment for the RtlRandomEx:
it is faster than RtlRandom() since it saves one multiplication, one addition and
one modulus operation. This almost doubles the performance since it halves the number of
clocks even on a pipelined Integer Unit such as the P6/ia64 processors i.e. ~ 52% perf gain.
Perhaps a math/statistics expert can tell me why that is a bad idea.
I didn't get it at first, either, and the Wikipedia article didn't do it for me. This explanation finally got me there: https://florian.github.io/reservoir-sampling/
Practically speaking, I might just allocate an array of 100 pointers. That's only 400 bytes. Then as you encounter each filename, allocate just enough memory for the actual length of the string (plus null terminator) and store the pointer in the array.
You still need to see all of the items once.
Imagine you have 2 items.
First one has 100% chance to be selected. So it does. Then the second has 50% chance to be selected. If it isn’t you effectively chosen the first one and have 50/50 chance to return either.
Now you add a third item. There is 50/50 chance of having either selected. And 1/3 chance of replacing the selection with the new one. Resulting in a 1/3 chance of selecting any of the three. (Because 1/2-1/6 = 1/3) 1/6 because there is 50% chance you will “steal” the selection.
I don't understand Microsoft. These guys solve the most mundane problems with most elegant solutions and with sound edge-case handling scenarios, then they destroy all the effort with subpar programming where it matters and with user hostile behavior where they can't botch it.
Different teams with different goals and different management
Not to mention the stack ranking policies that caused engineers to sabotage other people's work and avoid collaboration in order to keep themselves high on the stack in order to avoid being fired.
I get what you mean, but it's really hard for any organization this size to drive consistent quality across the board.
Yep..
And image files were, and continue to be, a huge exploit attack vector
However, I still remember Wine laughing at Windows for WMF exploit and end up being affected from the same exploit. Now, that was a good laugh.
I think it's true, but not sure if I'm just falling victim to false memories... help?
I configured an account for someone with an Asian last name and it chose the fortune cookie.
Probably not voodoo, but it never seemed 100% random. More like some correlation was being done.
https://jakeludington.com/2003/12/17/create_your_own_windows...
To me Windows 95/NT 4 is still the gold standard in Windows UI. It's certainly not the prettiest, that would be Windows 2000, but it was easy to use, easy to navigate and efficient with space.
>During the Luna studies, that people’s reaction to Luna was often, “Wow this would be a great UI for X,” where X was “my dad” or “my employees” or “my daughter”. People didn’t look at it as the UI for themselves; rather, they thought it was a great UI for somebody else.
(Luna is the name of the default look of Windows XP)
It's all been downhill from there as far as UX goes.
Its Vista. Like it or hate it. It’s Vista
nobody cares
On top of that, how often is it necessary to efficiently know the number of files in a directory while at the same time not caring about the files enough to list or display them? This algorithm is a special case where you could use the count of using a bit simpler code that ultimately would have the same file system API calls (since you cannot tell the FS to give you file #37 from that directory, so you'd have to use FindNextFile 37 times anyway, just like the sampling algorithm).
This is more-or-less unique to ZFS. Other file systems even on Linux and FreeBSD generally don't provide this behavior.
Most unix filesystems use inodes. inodes have the same format whether they represent a file or directory. So directory have a (usually unused) size member. NTFS doesn't use inodes, but the records in the MFT work the same way.
When adding or removing a file from a directory, you have to update the modification time of the folder, so you have to rewrite the entire inode anyway. Updating the size/file count at the same time would be free.
In my opinion the likely reason why file count isn't tracked is a lot more pedestrian: It wasn't tracked initially and we can never add it to existing file systems because the metadata would get out of sync if the FS was mounted on a kernel with no count support.
I base this assumption on the fact that many modern file systems do indeed keep track of the count.
> it’s more efficient because it reduces the amount of calls into the file system, which is where the bottleneck is
Upon reading it a few times I think the article is alluding to a crappy two-pass solution where you don't store a filename but instead an index into a directory, which is flawed anyway due to being racy.
If you are at picture 1, you have 100% chance of selecting it as the current winner.
If you are at picture 2, you have 1/2 chance of selecting it as the current winner, or 1/2 chance of keeping the previous fairly selected winner.
At picture 3, 1/3 chance of picking it, or 2/3 chance of retaining the previous fairly-selected winner. There are two of them, so 1/3 chance of each.
At picture n, you have a 1/n chance of picking it, or an (n-1)/n chance of retaining the previous fairly-selected winner. There are n-1 previous pictures, so all of them have had 1/n chance of being picked.
At every single step, there is the invariant of all pictures being considered that far having had an equal chance of being selected, and the next step always retains the invariant.
pics[Math.random() * len(pics)]
The picture selection algorithm's kind of single-pass iterator usage might have been more performant back in the XP days, as it avoids possibly expensive operations.
Modern CPU/other optimizations might make a multi-pass approach more performant due to better memory locality or other factors.
Even if you work on exciting things, the project will always have boring parts.
You'll need to develop these parts as well, so be prepared and show the same respect to all parts.
Most modern Windows code was written in 1995. Don't assume for one moment that it isn't in production Win11 today.
I had tons of "Visual Styles" back then and in the last XP days I opted for grayish Royal or Royale. It's such shame that MS has abandoned Watercolor theme - that was a middle ground: interface was updated and yet, still similar to classic design. And it was even in some elements flat before that style become a dominant. Luckily we're slowly moving away from that and I won't be missing it.
i kinda miss xp at a cultural level since it was a bit the end of that computing culture cycle (after that apple started to dominate and ubuiquitous computing influenced desktop ui)
When did Apple dominate? I'm not trying to hate on Apple here, but there's this weird belief that Apple have had a lead in personal computer OS market share at some point in the last few decades, and it isn't really true since about 1984.
You can argue that they should dominate, but that doesn't seem to have happened.
I eventually got used to it and ended up liking it.
For awhile I ran XP 64-bit though, that did do one thing 2000 couldn't do.