Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

What algorithm did Windows XP use to choose your initial user picture?

devblogs.microsoft.com

Post reply on HN
Print view View original

161–168 of 168 posts

Re: What algorithm did Windows XP use to choose your initial user picture?

#161

Post by pixl97 »

madibo3156 wrote: post #120
layer8 wrote: post #114

Earlier quoted context omitted.

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 i th 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.

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?

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.

Re: What algorithm did Windows XP use to choose your initial user picture?

#162

Post by petya415 »

lyorig wrote: post #27

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.

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.

Re: What algorithm did Windows XP use to choose your initial user picture?

#163

Post by amag »

nerdo wrote: post #141

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))));…

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.
[0]: https://github.com/tongzx/nt5src/blob/daad8a087a4e75422ec96b... [1]: https://github.com/tongzx/nt5src/blob/daad8a087a4e75422ec96b...

Re: What algorithm did Windows XP use to choose your initial user picture?

#164

Post by aqfamnzc »

petya415 wrote: post #162
lyorig wrote: post #27

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.

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.

Dave Plummer?

Re: What algorithm did Windows XP use to choose your initial user picture?

#166

Post by tyrust »

majorchord wrote: post #165

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.

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.

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/

Re: What algorithm did Windows XP use to choose your initial user picture?

#167

Post by majorchord »

tyrust wrote: post #166
majorchord wrote: post #165

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.

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. 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/

But wouldn't changing the probability be even more random?

Re: What algorithm did Windows XP use to choose your initial user picture?

#168

Post by Sophira »

kevin_thibedeau wrote: post #148
VCFundedGenYer wrote: post #124

Earlier quoted context omitted.

> And it's an old version of the OS anyway. Most modern Windows code was written in 1995. Don't assume for one moment that it isn't in production Win11 today.

You can still get windows 3 directory picker dialogs in obscure places like the ODBC data source utility.

You can even still get error messages referencing the CONFIG.SYS file, which hasn't been relevant for well over two decades at this point: https://www.reddit.com/r/sysadmin/comments/1wctbf3/throwback...
Post reply on HN