That is a case I only become aware of when I read blogs like this. Technically I could solve it the same way, but these days you have so many tasks on your desk, you don't think about the problem and implications at all and that awareness/discipline is drowned in the noise/unlearned over time.
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.
Man, every post from Raymond Chen regarding Windows internals is like a little Xmas. I wonder whether he has to ask someone for permission before publishing this knowledge, though.
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.
>Raymond has been involved in the evolution of Windows for more than 30 years. He occasionally appears on the Windows Dev Docs Twitter account to tell stories which convey no useful information.
This is a fun example of the cognitive switch you have to employ when first starting to program a computer. It's extremely easy for a human to pick at random one thing from a pile of things: you reach out your hand and grab it, maybe swirling them around on the table first to shuffle the order. For a computer, there's no direct analogy to that. They just can't do it. And the human process is nothing even slightly like the one the computer follows: we don't have to count the sets and iterate over them, or count the items and then generate a random number to pick the nth item, or risk picking a null item.
But the naive way of doing this also wouldn't really require two passes, right? It would just require more memory because you would first save all file names in an array (stopping at 100), then pick a random one in constant time.
How do you know how big your array has to be in a single pass? I don't think the WinXP source uses vectors or similarly ergonomic auto-growing arrays. You could preallocate an array big enough for 100 paths of length MAX_PATH, but that's a bit wasteful. And it doesn't sound like you'd actually end up with fewer lines of code (in that flavor of C++, in python it would be different)
Either that call would have to do the same (i.e., walking the files and counting), or you'd need some additional metadata in the directory entry to store how many files there are, requiring additional storage accesses for adding and removing files. Adding to that that both FAT32 and NTFS are quite old and had to run on older hardware. Cycles and disk accesses are not free.
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).
Not that it counters any point you're making, but ZFS displays the number of contained entries of a directory in the directory's size field; mind that . and .. are included, so you usually need to subtract 2 to get the count you actually want. I do find it useful sometimes to know the count without getting the listing; the former is a very inexpensive operation (since ZFS is keeping track of metadata like you suggested), the latter is expensive, potentially extremely with hundreds of thousands or more of entries.
This is more-or-less unique to ZFS. Other file systems even on Linux and FreeBSD generally don't provide this behavior.
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.
We had bigger problems back then, and the function ran considerably rarely when compared the other parts of the OS, so it was a valid assumption at that age.
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.
That's a matter of taste, but for many it was the Windows they used first and/or spend the most time on and there's a lot of love for that reason alone. I never used XP all that much, but I always changed the theme to the Windows 2000 look. I really didn't like the default, it looked unprofessional and clunky in my eyes. Upon release XP was also pretty universally mocked as a Fisher Price-like UI.
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.
Of course that's a matter of taste but Luna interface/theme made whole XP being more appealing to ordinary people - especially with these task-oriented elements. On the other hand, "classic" widgets had that strong bare-bone technical and functional look that made whole system scarier to some degree.
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.
win2k was peak for me. lean, functional, just a pinch of glitter here and there (short fade-ins). it was on par with the amazing stability brought by nt5 kernel.
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.
Took me years to like Windows XP. Hated the new start menu. I always kept installing Windows 2000 (or ME, probably because it could use Windows 98 drivers but look like Windows 2000).
I eventually got used to it and ended up liking it.
I always ran it with the 2000 style theme. That said XP offered me nothing over 2000 so 2000 is what I ran on my main machine since it used less ram but did all the same things, often a bit faster.
For awhile I ran XP 64-bit though, that did do one thing 2000 couldn't do.
It was at this moment I realized that people are talking about liking the non-classic-look XP. I always immediately put things in classic look, no grouped windows, etc.
The first Windows I used was 98, and I sure didn't miss the blocky grey menus nor the pixelated icons. Maybe it was Fisher Price-ish but the new rounded buttons and borders were way more appealing to me.
The "Windows Classic" look on XP is exceptionally ugly, because those 3D-rendered icons just do not belong on a Windows 2000-style grey background for menus or buttons. (I have recently had to test both these OSes in VMs…)
That is true, it looked completely off, as if no one really bothered to tests it and make it look nice. It got rid of the horrible window decoration of the default theme, but the start menu looked terrible.
>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)
What is amazing is the amount of consideration given to an issue which would escape the majority of users. It is surprising how complex an apparently easy process turns out when considering certain special cases.
On initial install, sure. But user accounts can also be created at arbitrary times. The user may have changed the set of photos in the intervening time and might even be editing the directory during profile creation.
> As a final safety check, the code stops after sampling 100 pictures. This avoids pathological behavior if somebody puts a million files in the Default Pictures directory
Because it would always return the first match in that case.
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.
Oh, I understand, should've examined more carefully, the count starts at 0 and increments, so random is not from the total but from the elements counted so far.
Thank you for writing this out, I didn't quite get what was going on at first. But then, to formalize the recursion from your example: let's assume we're at item n in the iterator, and at that point we've selected a winner from the previous n-1 items with equal probability, i.e. each item had a 1/(n-1) chance of being selected. The probability that item n will override it is 1/n. The probability that the old winner will remain selected is thus (n-1)/n. That means that the old winner remains selected with probability 1/(n-1) * (n-1)/n, which cancels out to 1/n, so each item is indeed selected with equal probability in the end.
No there is not. First element is defacto winner, but you still have to loop through the rest with 1/n chance of being selected to fully give each element a chance of winner selection
The len(pics) can be O(n), especially if iterators are used like here. Also, an O(1) lookup would require a previous O(n) pass over the data anyway.
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.
On count == 1, the winner gets set to the first element, true. But the function does not return yet! So the value might get overwritten during the remainder of the for-loop.
There's no way my memory of this is reliable anymore, but I also remember my administrator account being chess pieces (and my user account being an orange fish).
That is a case I only become aware of when I read blogs like this. Technically I could solve it the same way, but these days you have so many tasks on your desk, you don't think about the problem and implications at all and that awareness/discipline is drowned in the noise/unlearned over time.
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.
I love the understated "some time ago" linking to a 2004 blog post. Raymond has been at this a long time :-)
Man, every post from Raymond Chen regarding Windows internals is like a little Xmas. I wonder whether he has to ask someone for permission before publishing this knowledge, though.
Easier for a guy like him to be forgiven than to ask permission.
Being tenured and one of the top engineers in your company with a very proven track record gives you quite a bit more freedom.
I also wonder what his thoughts on “modern Windows” are
His silence speaks a thousand words.
Yeah I agree. Mr. Chen strikes me as too professional to put his employer on blast like that, but he's likely not a fan.
For those interested, here's the actual code Chen talks about: https://github.com/tongzx/nt5src/blob/daad8a087a4e75422ec96b...
I don't see how this is supposedly more efficient than the easier approach of listing all files and choosing a single random number in 1..n
You have to allocate memory and free it.
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.
Didn't know that NT5 source is available for the public. Why Microsoft does not ban/delete it on GitHub?
It'll pop up elsewhere so might as well keep it online on their servers. And it's an old version of the OS anyway.
If it were the Windows 11 source, it'd get nuked immediately
They are usually deleted, maybe this one hasn't got popular enough yet.
It's been around for six years; at this point, I imagine any damage it could have done has been done already.
>Raymond has been involved in the evolution of Windows for more than 30 years. He occasionally appears on the Windows Dev Docs Twitter account to tell stories which convey no useful information.
That made me chuckle too. No utility, but I did find it interesting.
This is a fun example of the cognitive switch you have to employ when first starting to program a computer. It's extremely easy for a human to pick at random one thing from a pile of things: you reach out your hand and grab it, maybe swirling them around on the table first to shuffle the order. For a computer, there's no direct analogy to that. They just can't do it. And the human process is nothing even slightly like the one the computer follows: we don't have to count the sets and iterate over them, or count the items and then generate a random number to pick the nth item, or risk picking a null item.
The times when people spent an extra brain cycle to avoid billions of second passes.
But the naive way of doing this also wouldn't really require two passes, right? It would just require more memory because you would first save all file names in an array (stopping at 100), then pick a random one in constant time.
How do you know how big your array has to be in a single pass? I don't think the WinXP source uses vectors or similarly ergonomic auto-growing arrays. You could preallocate an array big enough for 100 paths of length MAX_PATH, but that's a bit wasteful. And it doesn't sound like you'd actually end up with fewer lines of code (in that flavor of C++, in python it would be different)
It's somewhat odd that filesystems don't have a call to tell you how many files are in a folder.
Either that call would have to do the same (i.e., walking the files and counting), or you'd need some additional metadata in the directory entry to store how many files there are, requiring additional storage accesses for adding and removing files. Adding to that that both FAT32 and NTFS are quite old and had to run on older hardware. Cycles and disk accesses are not free.
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).
Not that it counters any point you're making, but ZFS displays the number of contained entries of a directory in the directory's size field; mind that . and .. are included, so you usually need to subtract 2 to get the count you actually want. I do find it useful sometimes to know the count without getting the listing; the former is a very inexpensive operation (since ZFS is keeping track of metadata like you suggested), the latter is expensive, potentially extremely with hundreds of thousands or more of entries.
This is more-or-less unique to ZFS. Other file systems even on Linux and FreeBSD generally don't provide this behavior.
I feel like there would either be too many locks or too much contention on something like /var/log or /tmp if that API was ever exposed to userspace.
just have it count how many times del cmd runs successfully /s
Claude, is that you?
The good old Aqua Regia test.
Honestly,
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.
They're a very large organization with engineers of widely varying skills in projects with very different timelines.
I get what you mean, but it's really hard for any organization this size to drive consistent quality across the board.
> // Assume everything in the dir is a vaild image file
Yep..
And image files were, and continue to be, a huge exploit attack vector
We had bigger problems back then, and the function ran considerably rarely when compared the other parts of the OS, so it was a valid assumption at that age.
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.
They simply find some problems more interesting to solve than others.
Just like the rest of us.
A couple of screenshots would've been useful for the post-millennial generations that never got to see the "beauty" (cough) of XP.
Here's a blog post from 2003 with beautiful pictures.
https://jakeludington.com/2003/12/17/create_your_own_windows...
XP is Microsoft's prettiest OS by far.
That's a matter of taste, but for many it was the Windows they used first and/or spend the most time on and there's a lot of love for that reason alone. I never used XP all that much, but I always changed the theme to the Windows 2000 look. I really didn't like the default, it looked unprofessional and clunky in my eyes. Upon release XP was also pretty universally mocked as a Fisher Price-like UI.
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.
Of course that's a matter of taste but Luna interface/theme made whole XP being more appealing to ordinary people - especially with these task-oriented elements. On the other hand, "classic" widgets had that strong bare-bone technical and functional look that made whole system scarier to some degree.
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.
win2k was peak for me. lean, functional, just a pinch of glitter here and there (short fade-ins). it was on par with the amazing stability brought by nt5 kernel.
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)
"after that apple started to dominate"
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.
Maybe they mean culturally.
Took me years to like Windows XP. Hated the new start menu. I always kept installing Windows 2000 (or ME, probably because it could use Windows 98 drivers but look like Windows 2000).
I eventually got used to it and ended up liking it.
I always ran it with the 2000 style theme. That said XP offered me nothing over 2000 so 2000 is what I ran on my main machine since it used less ram but did all the same things, often a bit faster.
For awhile I ran XP 64-bit though, that did do one thing 2000 couldn't do.
IIRC correctly, XP’s stability greatly increased after Service Pack 2 was published.
XP Service Pack 2 was in essence a different OS.
It was at this moment I realized that people are talking about liking the non-classic-look XP. I always immediately put things in classic look, no grouped windows, etc.
The first Windows I used was 98, and I sure didn't miss the blocky grey menus nor the pixelated icons. Maybe it was Fisher Price-ish but the new rounded buttons and borders were way more appealing to me.
The "Windows Classic" look on XP is exceptionally ugly, because those 3D-rendered icons just do not belong on a Windows 2000-style grey background for menus or buttons. (I have recently had to test both these OSes in VMs…)
That is true, it looked completely off, as if no one really bothered to tests it and make it look nice. It got rid of the horrible window decoration of the default theme, but the start menu looked terrible.
https://devblogs.microsoft.com/oldnewthing/20040331-00/?p=39...
>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)
I feel Vista was by far the best. 7 simplified it a bit, but that Start orb and black taskbar on Vista, man, that was glorious.
I found each of 2000, XP, and 7 to be excellent in its own unique way. I'd be happy with any of them. But it also felt exciting to upgrade.
It's all been downhill from there as far as UX goes.
Perhaps with the Zune theme installed.
I like the installation music :-)
"Welcome to Windows 98" with the church bell and sick bass intro can never be beaten. It's cut short unfortunately.
Ehem... nothing beats the beauty and simplicity of Win 95 :)
Didn't that design appear first in 3.51?
You mean 7 ;)
Windows 7 was certainly pretty, but I still think that W2000 was peak Windows UI (and I've been around since Windows 2.0)
Windows 7 fixed Vista a bit, but the Aero windows were never pretty and the non-Aero decorations were painfully obvious a placeholder.
I thought it looked great :-/
I don't see how that's relevant? Article is about the RNG implementation, it doesn't matter what the profile pictures are.
> I don't see how that's relevant?
nobody cares
What is amazing is the amount of consideration given to an issue which would escape the majority of users. It is surprising how complex an apparently easy process turns out when considering certain special cases.
100 seems like a very unnecessarily low limit, even for the time
It's well above the number of images that were in the applicable folder by default, so seems pretty appropriate to me.
Why they made it that complex?
A simple rand/mod based on first character of username should be sufficient?
because you don't know the number of images before running the code so no number to do the mod part
Why wouldn't you know that? It's a set of preloaded stock photos, it's always gonna be the same number.
On initial install, sure. But user accounts can also be created at arbitrary times. The user may have changed the set of photos in the intervening time and might even be editing the directory during profile creation.
> As a final safety check, the code stops after sampling 100 pictures. This avoids pathological behavior if somebody puts a million files in the Default Pictures directory
It’s a directory. You could add pictures to it, and we did in our image layout (mainly for fun, but they wanted the logo as one).
At compile time of when the pr department decided to change it?
So users Adam, Anne and Archie all have the same profile image?
OK - then use the first two characters :-D
How is that simpler?
because its a built-in one-liner call then?
Why doesn't it return on the first match?
Because it would always return the first match in that case.
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.
Oh, I understand, should've examined more carefully, the count starts at 0 and increments, so random is not from the total but from the elements counted so far.
Thank you for writing this out, I didn't quite get what was going on at first. But then, to formalize the recursion from your example: let's assume we're at item n in the iterator, and at that point we've selected a winner from the previous n-1 items with equal probability, i.e. each item had a 1/(n-1) chance of being selected. The probability that item n will override it is 1/n. The probability that the old winner will remain selected is thus (n-1)/n. That means that the old winner remains selected with probability 1/(n-1) * (n-1)/n, which cancels out to 1/n, so each item is indeed selected with equal probability in the end.
exactly. There is something wrong with the code snippet.
No there is not. First element is defacto winner, but you still have to loop through the rest with 1/n chance of being selected to fully give each element a chance of winner selection
Yeah I think the "wrong feeling" is just that this could, in theory, be O(1) with something like:
... assuming that random() gives you a number from 0..1 - but that's why it feels "wrong".The len(pics) can be O(n), especially if iterators are used like here. Also, an O(1) lookup would require a previous O(n) pass over the data anyway.
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.
len(pics) either already knows about the length or it needs to count so it’s O(n)
I re-examined it, the count changes, that's why it works. The random is not between 1 and total, it's between 1 and current count.
On count == 1, the winner gets set to the first element, true. But the function does not return yet! So the value might get overwritten during the remainder of the for-loop.
Does it also check existing users so you don't match one?
It doesn't: https://github.com/tongzx/nt5src/blob/daad8a087a4e75422ec96b...
Some say the Admin account defaulted to a chessboard.
I think it's true, but not sure if I'm just falling victim to false memories... help?
The account named "Administrator" that Windows created for you always had the chess piece.
There's no way my memory of this is reliable anymore, but I also remember my administrator account being chess pieces (and my user account being an orange fish).
It might be that the randomization code was bypassed in some cases - like creating an account in safe boot mode or similar.
It makes sense. The chess piece is the first profile picture in the list.
I remember it like that too. Or is it Mandela effect?
The Magnus effect? :)
I'm disappointed that it is not influenced by the username ... "You sound like a skateboard kinda person"