From The Old New Thing · Raymond Chen · · 1 min
How Windows XP Picked Your Initial Profile Picture
A peek inside the clever single-pass algorithm that chose your default Windows XP user picture without slowing down your system.
In brief
A peek inside the clever single-pass algorithm that chose your default Windows XP user picture without slowing down your system. Reservoir sampling allows uniform random selection from a stream of unknown size in a single pass without needing to pre-count items. Originally reported by The Old New Thing.
Random pictures used system uptime
Windows XP picked user pictures from a default directory using the RtlRandomEx function. It seeded the generator with GetTickCount, which measures system uptime.
“The random number generator is our friend RtlRandomEx , using the current value of GetTickCount() as the initial seed.”
One pass beat counting files first
A basic approach counts every file in a folder before picking a target. Windows XP avoided this extra pass to reduce file system calls and prevent speed bottlenecks.
“it’s more efficient because it reduces the amount of calls into the file system, which is where the bottleneck is.”
Single passes handled moving files
Reading directory contents once also protected the process from bugs. If files were added or removed while the code was running, a two-pass algorithm could easily fail.
“the one-pass algorithm avoids complications if the number of files in the directory changes while the code is running.”
Reservoir sampling powered the choice
The selection used reservoir sampling where k equals 1. As the system read each item, the nth item had a 1 in n chance to replace the currently selected picture.
“The one-pass algorithm is a special case of reservoir sampling , where k is 1.”
Safety limits capped the file search
As a final safeguard, the process stopped inspecting pictures after 100 files. This kept the system responsive even if a user dumped thousands of images into the default folder.
“As a final safety check, the code stops after sampling 100 pictures.”
The key point
Reservoir sampling allows uniform random selection from a stream of unknown size in a single pass without needing to pre-count items.
