Rendered at 21:51:26 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
mawadev 1 days ago [-]
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.
Its not like windows is the pinnacle of software craftsmanship.
kevin_thibedeau 1 days ago [-]
I'd bet this bug also shows up in Vista file explorer with auto arrange disabled. Nobody will ever need more than 100 icons on their 800x600 workstation. Ship it.
Aurornis 1 days ago [-]
Two things that have helped me with quickly recognizing these situations:
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.
CamperBob2 1 days ago [-]
How many user pictures are there to choose from, though? This is a nice, elegant way to sample from the set, but the nature, size, and frequency of the problem don't justify more than five or ten seconds' or thought and one or two minutes of coding.
dwattttt 1 days ago [-]
But multiplied by the number of times it'll run on the planet, and you have a surprisingly big impact.
mawadev 1 days ago [-]
Exactly this, if you count the amount of time the windows 11 context menu needs to pop up and then the second click to get to the old context menu across the entire globe for a month, you would get an insane amount of time and cycles wasted
CamperBob2 1 days ago [-]
I guess I'd do it once, the slow and easy way, and cache the result. But that's just me.
dwattttt 1 days ago [-]
The billions of times aren't repeated times for the same person, it's because it's been done for the first time billions of times. This is the "choose a user's initial profile picture". They're not randomly changing it.
lyorig 1 days ago [-]
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.
cloudfudge 1 days ago [-]
It's been many years since I talked to him, but he's an extremely by-the-book guy, so I'm sure he has a process for clearing everything he writes. His reputation does probably provide him a lot of leeway, though. He also has a queue of oldnewthing articles about a mile long and we could probably get years' worth of articles after his death if they let them run.
Hydraulix989 1 days ago [-]
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.
xp84 1 days ago [-]
Yeah - he's more likely the guy that would be giving that kind of permission to someone more junior.
alex_suzuki 1 days ago [-]
I also wonder what his thoughts on “modern Windows” are
dyllon 1 days ago [-]
His silence speaks a thousand words.
bigstrat2003 1 days ago [-]
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.
jasomill 19 hours ago [-]
I imagine he's fine with it in terms of job satisfaction at the very least, as far as I can tell his areas of expertise are shell and related COM internals, and he clearly takes pride in the nuances of cleaning up other peoples' messes, and if there are two things that have remained constant in Windows programming over the past 30 years, it's COM and messes.
98codes 1 days ago [-]
It's not as if he's stopped working on Windows since 2000.
darig 1 days ago [-]
[dead]
petya415 1 days ago [-]
Isn't there a guy on youtube that spills tea about the internals of old windows systems? And I suspect their NDAs about XP expired years ago - I don't see much harm in sharing these herbivore algorithms. Very cute post tho.
jasomill 19 hours ago [-]
Forget YouTube. Google "windows xp source code leaks" and one of the top hits is a six-year old GitHub repo.
Which sort of makes sense. I'm not sure technical trade secrets have ever played much of a role in Microsoft's success.
With or without source code, programmers have been digging at the internals of Microsoft OSes for fun and profit since the DOS days, and Microsoft has always seemed to recognize that developers and customers relying on the undocumented nuances of their products benefits them far more than understanding them benefits their competitors.
21 hours ago [-]
aqfamnzc 1 days ago [-]
Dave Plummer?
reddalo 11 hours ago [-]
I used to follow him, but then I've read some controversial news about him...
fred_is_fred 1 days ago [-]
If you ask for permission on something like this the answer is always no.
Why remove things, storage is only getting cheaper /s
Sopel 1 days ago [-]
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
bonzini 1 days ago [-]
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.
Sopel 1 days ago [-]
yes, you would have to allocate space for up to 100 file paths, but the article says
> 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.
impoppy 1 days ago [-]
>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.
carrja99 1 days ago [-]
That made me chuckle too. No utility, but I did find it interesting.
VCFundedGenYer 1 days ago [-]
A true Microsoft drone to the end.
scrumper 1 days ago [-]
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.
rhplus 1 days ago [-]
I think this article highlights more the importance of understanding system limits in the 1990s versus today. No-one would care to much today if the code review for this feature had “files.count()” or whatever in it, but in the mid 90s that would have been a huge performance red flag because a user would literally hear their hard drive clicking away and see the blinkenlights.
layer8 1 days ago [-]
The problem isn’t counting the files (the algorithm in the article also counts the files), but that if you determine that you want to use the ith file only after counting all files, you have to iterate over the whole directory again (or over expected half of it) to find that file.
madibo3156 1 days ago [-]
The mechanism is interesting, but I'm not fully understanding the importance. We say it was done this way because a user would appreciate the speedup. The difference is one traversal versus expected one and one-half traversals. How slow was this traversal at the time for this difference to be significant?
layer8 1 days ago [-]
It will depend on details like file system fragmentation (Windows XP could run on FAT32), but it could conceivably make a perceptible difference on a slow HDD when there are many pictures in the directory. You also have to check more error cases, for when the second iteration fails for some reason. The mindset was probably "why complicate the code with multiple iterations and make it less efficient?" when the efficient solution is straightforward and arguably simpler.
linepogl 1 days ago [-]
Apart from the performance issues, it also prevents a bug. If some files get deleted between the first and the second pass, then you end up with unexpected behaviour and probably a crash.
sltkr 1 days ago [-]
The current implementation has the same race condition: the sampled file may be deleted by the time SHSetUserPicturePath() is called.
layer8 23 hours ago [-]
Yes, but the the implementation with the additional iteration also has to have extra checks for that iteration, because it can't blindly iterate to the ith file, as there may not be i files anymore. So the implementation gets more complex overall.
pixl97 1 days ago [-]
Hard drives are measured in hundreds of IOPS at most. Then you have the 40 billion other things trying to eat those IOPS at startup.
ajsnigrutin 1 days ago [-]
That's why now we need gigabytes of ram to do the same thing we managed in 128Mb back then. I mean sure, there's an AI chatbot in your PDF viewer and ads in your start menu, but the functionality of many daily things is still the same.
cgio 1 days ago [-]
The times when people spent an extra brain cycle to avoid billions of second passes.
jasonvorhe 2 days ago [-]
A couple of screenshots would've been useful for the post-millennial generations that never got to see the "beauty" (cough) of XP.
moritzwarhier 1 days ago [-]
Here's a blog post from 2003 with beautiful pictures.
These pictures are so compressed they depict color rasterization artifacts more than the Luna UI style.
Maken 1 days ago [-]
XP is Microsoft's prettiest OS by far.
mrweasel 1 days ago [-]
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.
pndy 1 days ago [-]
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.
agumonkey 1 days ago [-]
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)
Intermernet 1 days ago [-]
"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.
agumonkey 1 days ago [-]
The mac os x and iphone era dictated UI and UX for a while. I wasn't clear that I wasn't talking about market share.
2muchcoffeeman 1 days ago [-]
Maybe they mean culturally.
unregistereddev 1 days ago [-]
I remember Apple products being the realm of graphics designers, videographers, and other art professionals back in the XP days. I thought they went mainstream later, as Windows Vista coincided with the iPhone release.
Maken 1 days ago [-]
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.
afzalive 1 days ago [-]
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.
deltoidmaximus 1 days ago [-]
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.
stingraycharles 1 days ago [-]
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.
alex_suzuki 1 days ago [-]
IIRC correctly, XP’s stability greatly increased after Service Pack 2 was published.
gschizas 1 days ago [-]
XP Service Pack 2 was in essence a different OS.
21 hours ago [-]
1 days ago [-]
TazeTSchnitzel 1 days ago [-]
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…)
mrweasel 1 days ago [-]
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)
YPPH 1 days ago [-]
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.
delta_p_delta_x 1 days ago [-]
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.
kasabali 1 days ago [-]
IMO Aero parts looked phenomenal but older Win32 parts like toolbars etc. didn't fit and looked odd
amiga-workbench 1 days ago [-]
Perhaps with the Zune theme installed.
fractal618 1 days ago [-]
I like the installation music :-)
rzzzt 1 days ago [-]
"Welcome to Windows 98" with the church bell and sick bass intro can never be beaten. It's cut short unfortunately.
meerita 1 days ago [-]
Ehem... nothing beats the beauty and simplicity of Win 95 :)
edoceo 1 days ago [-]
Didn't that design appear first in 3.51?
TheAmazingRace 1 days ago [-]
Only if you install the Shell Technology Preview from Microsoft. NT 3.51 came with the classic Win 3.x look and feel as well as Program Manager.
edoceo 1 days ago [-]
Yea, it was 4.0, oops
sunaookami 1 days ago [-]
You mean 7 ;)
medwards666 1 days ago [-]
Windows 7 was certainly pretty, but I still think that W2000 was peak Windows UI
(and I've been around since Windows 2.0)
Maken 1 days ago [-]
Windows 7 fixed Vista a bit, but the Aero windows were never pretty and the non-Aero decorations were painfully obvious a placeholder.
sunaookami 1 days ago [-]
Aero was pretty though.
ksncksndsh 1 days ago [-]
That’s Vista. And there’s no contest whatsoever. They’ve never been able to again achieve the perfect balance of elegance and functionality that Vista’s UI had.
Its Vista. Like it or hate it. It’s Vista
CalRobert 1 days ago [-]
I thought it looked great :-/
PalmPilotProMax 1 days ago [-]
I don't see how that's relevant? Article is about the RNG implementation, it doesn't matter what the profile pictures are.
lirolero 1 days ago [-]
> I don't see how that's relevant?
nobody cares
adrianmonk 1 days ago [-]
> it’s more efficient because it reduces the amount of calls into the file system
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.)
bombela 1 days ago [-]
less work is always cheaper. no matter what.
sltkr 1 days ago [-]
It's not _strictly_ less work though: reservoir sampling requires generating many more random numbers. As usual, it's a tradeoff.
ape4 1 days ago [-]
It's somewhat odd that filesystems don't have a call to tell you how many files are in a folder.
ygra 1 days ago [-]
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).
chungy 1 days ago [-]
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.
wongarsu 1 days ago [-]
ZFS being a copy-on-write fs probably made the relative cost of that feature much cheaper
tredre3 1 days ago [-]
> 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.
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.
eventualcomp 1 days ago [-]
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.
conorcleary 1 days ago [-]
just have it count how many times del cmd runs successfully /s
saagarjha 1 days ago [-]
Claude, is that you?
1 days ago [-]
xnickb 1 days ago [-]
The good old Aqua Regia test.
rietta 1 days ago [-]
I love the understated "some time ago" linking to a 2004 blog post. Raymond has been at this a long time :-)
SoftTalker 1 days ago [-]
I love that 2004 sounds like "some time ago" to some people. Seems like yesterday to me.
rietta 1 days ago [-]
Isn't that the truth! I remember it very, very well. Vividly even.
Aditya_0315 1 days ago [-]
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.
ang_cire 1 days ago [-]
My eyes glazed over when I saw "recursively", and I had to re-read the last couple paragraphs again to grok it, and it's very cool.
wky 1 days ago [-]
A mentally simpler, though slightly biased algorithm is for each item, randomly generate a uint64 (arbitrary bit size) and switch to the new item if and only if the number generated is greater than or equal to all previously seen numbers. The end result is equivalent to randomly generating a number for each item and picking the item with the largest associated number.
aimor 8 hours ago [-]
You could even calculate the 100 random numbers up front and potentially stop iterating early.
nerdo 1 days ago [-]
There's a better way to do this, you use inverse CDF to avoid all the RNG calls.
Generate a random number, then skip items until you reach that number:
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();
}
}
canucker2016 1 days ago [-]
Back in the day, Windows OS kernel programming avoided use of floating point numbers - certainly transcendental functions would've been frowned upon - when CPUs didn't include an FPU.
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.
amag 1 days ago [-]
Better in which way? It doesn't seem like the RNG is much of a bottleneck[0]. So this code is just more complicated than the original[1] IMO. It is also most likely more costly by involving a bunch of extra divs, logs and (for XP-level HW) floating points, though admittedly the bottleneck on XP-level HW was most likely still the disk.
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.
100 seems like a very unnecessarily low limit, even for the time
daveoc64 1 days ago [-]
It's well above the number of images that were in the applicable folder by default, so seems pretty appropriate to me.
cpeterso 20 hours ago [-]
Raymond’s selectRandomFromIterator algorithm requires iterating over all the files. It seems like querying the file system for the number of files in a directory should be an O(1) operation. Then you just select random number N between [1, number of files] and iterate to the Nth file.
Why does Raymond assume counting the files is an O(n) operation?
orf 19 hours ago [-]
Because counting the files is not an O(1) operation? It would be cool if it was, but that’s not reality?
ulrikrasmussen 1 days ago [-]
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.
wongarsu 1 days ago [-]
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)
adrianmonk 1 days ago [-]
You could use a linked list.
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.
ulrikrasmussen 19 hours ago [-]
That will require a second pass though, because you have to free all your strings again.
ulrikrasmussen 1 days ago [-]
Yes, you could allocate it on the stack. I think back then (still?) a filename could be at most 260 characters, each encoded with 16 bits, so about 52k of stack allocation.
wongarsu 1 days ago [-]
52k on the stack is pretty significant, given Windows defaults to just 1MB stack size per thread
wat10000 1 days ago [-]
Depends on whether your naive approach prioritizes time or space.
The solution posted still requires O(n) calls to your random number generator.
You can do it in something like O(log n) calls while still sticking to a single forward only pass.
(But compared to reading the filesystem the rng calls were probably treated as free.)
majorchord 1 days ago [-]
Wouldn't it be even more random (and randomly faster) to break out of the while loop when a winner is found? That way you are not always iterating over the entire list.
Perhaps a math/statistics expert can tell me why that is a bad idea.
tyrust 24 hours ago [-]
If you break early, then you haven't given items later in the list the chance to be selected. You need to go through the entire list in order for every item to have an equal probability of selection.
But wouldn't changing the probability be even more random?
bspammer 22 hours ago [-]
If you read the "Adapting Probabilities" section of the link above, there's a nice explanation of why changing the probability works.
Crestwave 16 hours ago [-]
The first iteration has a 100% chance of being marked as a winner. It only balances out to the same odds as a random selection because of the chances of it getting overwritten by the succeeding files.
dsego 1 days ago [-]
Why doesn't it return on the first match?
yoz-y 1 days ago [-]
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.
Elte 1 days ago [-]
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.
Anon_troll 1 days ago [-]
An alternative wording for the same idea:
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.
matsemann 1 days ago [-]
This feels very analogous to the three doors puzzle.
dsego 1 days ago [-]
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.
quentinkent1 1 days ago [-]
exactly. There is something wrong with the code snippet.
arpadav 1 days ago [-]
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
fschuett 1 days ago [-]
Yeah I think the "wrong feeling" is just that this could, in theory, be O(1) with something like:
pics[Math.random() * len(pics)]
... assuming that random() gives you a number from 0..1 - but that's why it feels "wrong".
Anon_troll 1 days ago [-]
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.
akdev1l 1 days ago [-]
len(pics) either already knows about the length or it needs to count so it’s O(n)
kleiba2 1 days ago [-]
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.
dsego 1 days ago [-]
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.
bayindirh 1 days ago [-]
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.
wongarsu 1 days ago [-]
That's simple. The Windows Kernel is a collection of mostly elegant solutions, with a strong peppering of backwards-compatibility cruft, all the way from NT3 to Windows 11. The Windows userland received a lot of effort until about Windows XP, and since then is a collection of subpar programming, half-finished projects and user-hostile patterns (with some notable exceptions)
Different teams with different goals and different management
Sohcahtoa82 1 days ago [-]
> 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.
airstrike 1 days ago [-]
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.
waz0wski 1 days ago [-]
> // Assume everything in the dir is a vaild image file
Yep..
And image files were, and continue to be, a huge exploit attack vector
bayindirh 1 days ago [-]
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.
amelius 1 days ago [-]
They simply find some problems more interesting to solve than others.
Just like the rest of us.
amelius 1 days ago [-]
(Perhaps it shows that Apple engineers are pushed to grind at the boring problems more; therefore maybe it is better to work at Microsoft)
bayindirh 1 days ago [-]
Early in my career, I have read a blog post from someone senior about boring/entertaining work. In short it stated to following:
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.
So, I'd personally rather work on all parts equally well rather than winging boring parts and create something subpar.
amelius 1 days ago [-]
Maybe. By the way, I chose Apple as an example but their software is just about as bad, only slightly better.
bombcar 1 days ago [-]
Does it also check existing users so you don't match one?
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?
TazeTSchnitzel 1 days ago [-]
The account named "Administrator" that Windows created for you always had the chess piece.
bhaney 1 days ago [-]
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).
abhinavk 1 days ago [-]
I remember it like that too. Or is it Mandela effect?
NitpickLawyer 1 days ago [-]
The Magnus effect? :)
bombcar 1 days ago [-]
It might be that the randomization code was bypassed in some cases - like creating an account in safe boot mode or similar.
xx_ns 1 days ago [-]
It makes sense. The chess piece is the first profile picture in the list.
VVIQ2 1 days ago [-]
That's clever. I wonder if this was done by an intern during his summer internship :)
thenthenthen 19 hours ago [-]
Some example images would have been nice!
frou_dh 1 days ago [-]
I'm disappointed that it is not influenced by the username ... "You sound like a skateboard kinda person"
iJohnDoe 1 days ago [-]
Interesting topic.
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.
vishnuaniyan 1 days ago [-]
[dead]
1 days ago [-]
KellyCriterion 1 days ago [-]
Why they made it that complex?
A simple rand/mod based on first character of username should be sufficient?
lentil_soup 1 days ago [-]
because you don't know the number of images before running the code so no number to do the mod part
moffkalast 1 days ago [-]
Why wouldn't you know that? It's a set of preloaded stock photos, it's always gonna be the same number.
elgertam 1 days ago [-]
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.
throwaway219450 1 days ago [-]
I thought the same thing, and then wondered if this must be an enterprise problem, because what home user adds loads of icons - so many that IO becomes a concern - and also wants them to be randomly assigned to other family members?
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.
herywort 1 days ago [-]
> 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
bombcar 1 days ago [-]
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).
consp 1 days ago [-]
At compile time of when the pr department decided to change it?
nkrisc 1 days ago [-]
So users Adam, Anne and Archie all have the same profile image?
KellyCriterion 1 days ago [-]
OK - then use the first two characters :-D
sltkr 1 days ago [-]
So Adam, Adele, and Adrian all have the same profile image?
KellyCriterion 14 hours ago [-]
The the thing is:Most Adams/Adeles/Adrians wouldnt even notice
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.
Which sort of makes sense. I'm not sure technical trade secrets have ever played much of a role in Microsoft's success.
With or without source code, programmers have been digging at the internals of Microsoft OSes for fun and profit since the DOS days, and Microsoft has always seemed to recognize that developers and customers relying on the undocumented nuances of their products benefits them far more than understanding them benefits their competitors.
If it were the Windows 11 source, it'd get nuked immediately
Most modern Windows code was written in 1995. Don't assume for one moment that it isn't in production Win11 today.
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.
> 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.
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.
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.
>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
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.)
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.
selectRandomFromIteratorOptimized(iterator) { if (!iterator.moveNext()) { return null; }
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:
[0]: https://github.com/tongzx/nt5src/blob/daad8a087a4e75422ec96b... [1]: https://github.com/tongzx/nt5src/blob/daad8a087a4e75422ec96b...Why does Raymond assume counting the files is an O(n) operation?
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 can do it in something like O(log n) calls while still sticking to a single forward only pass.
(But compared to reading the filesystem the rng calls were probably treated as free.)
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/
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.
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.
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.
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.
Just like the rest of us.
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.
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.