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

151–160 of 170 posts

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

#151

Post by canucker2016 »

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

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.

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

#152

Post by adrianmonk »

wongarsu wrote: post #104
ulrikrasmussen wrote: post #94

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)

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.

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

#153

Post by bombela »

adrianmonk wrote: post #149

> 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 absolutel…

less work is always cheaper. no matter what.

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

#154

Post by CamperBob2 »

mawadev wrote: post #145
dwattttt wrote: post #142

Earlier quoted context omitted.

But multiplied by the number of times it'll run on the planet, and you have a surprisingly big impact.

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

I guess I'd do it once, the slow and easy way, and cache the result. But that's just me.

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

#155

Post by sltkr »

linepogl wrote: post #136
madibo3156 wrote: post #120

Earlier quoted context omitted.

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?

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.

The current implementation has the same race condition: the sampled file may be deleted by the time SHSetUserPicturePath() is called.

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

#156

Post by sltkr »

bombela wrote: post #153
adrianmonk wrote: post #149

> 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 absolutel…

less work is always cheaper. no matter what.

It's not _strictly_ less work though: reservoir sampling requires generating many more random numbers. As usual, it's a tradeoff.

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

#157

Post by sltkr »

KellyCriterion wrote: post #88
nkrisc wrote: post #52

Earlier quoted context omitted.

So users Adam, Anne and Archie all have the same profile image?

OK - then use the first two characters :-D

So Adam, Adele, and Adrian all have the same profile image?

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

#159

Post by wat10000 »

ulrikrasmussen wrote: post #94

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.

Depends on whether your naive approach prioritizes time or space.

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

#160

Post by dwattttt »

CamperBob2 wrote: post #154
mawadev wrote: post #145

Earlier quoted context omitted.

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

I guess I'd do it once, the slow and easy way, and cache the result. But that's just me.

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.
Post reply on HN