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

devblogs.microsoft.com

335 points by soheilpro 15 hours ago


mawadev - 13 hours 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.

lyorig - 13 hours 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.

EMIRELADERO - 12 hours ago

For those interested, here's the actual code Chen talks about: https://github.com/tongzx/nt5src/blob/daad8a087a4e75422ec96b...

impoppy - 12 hours 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.

scrumper - 10 hours 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.

cgio - 13 hours ago

The times when people spent an extra brain cycle to avoid billions of second passes.

adrianmonk - 5 hours 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.)

majorchord - 2 hours 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.

jasonvorhe - 14 hours ago

A couple of screenshots would've been useful for the post-millennial generations that never got to see the "beauty" (cough) of XP.

ape4 - 12 hours ago

It's somewhat odd that filesystems don't have a call to tell you how many files are in a folder.

ang_cire - 7 hours 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.

rietta - 9 hours ago

I love the understated "some time ago" linking to a 2004 blog post. Raymond has been at this a long time :-)

nerdo - 6 hours 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();
    }
}
Aditya_0315 - 11 hours 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.

ulrikrasmussen - 10 hours 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.

bhaney - 14 hours ago

100 seems like a very unnecessarily low limit, even for the time

wky - 10 hours 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.

dsego - 11 hours ago

Why doesn't it return on the first match?

bayindirh - 11 hours 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.

VVIQ2 - 3 hours ago

That's clever. I wonder if this was done by an intern during his summer internship :)

bombcar - 13 hours ago

Does it also check existing users so you don't match one?

moritzwarhier - 14 hours ago

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?

iJohnDoe - 6 hours 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.

frou_dh - 11 hours ago

I'm disappointed that it is not influenced by the username ... "You sound like a skateboard kinda person"

vishnuaniyan - 11 hours ago

[dead]

- 11 hours ago
[deleted]
KellyCriterion - 13 hours ago

Why they made it that complex?

A simple rand/mod based on first character of username should be sufficient?