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

141–150 of 167 posts

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

#141

Post by nerdo »

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

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

#142

Post by dwattttt »

CamperBob2 wrote: post #140
mawadev wrote: post #20

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…

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.

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

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

#143

Post by tredre3 »

ygra wrote: post #60
ape4 wrote: post #50

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

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…

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

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

#144

Post by Sopel »

bonzini wrote: post #90
Sopel wrote: post #87

Earlier quoted context omitted.

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

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.

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.

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

#145

Post by mawadev »

dwattttt wrote: post #142
CamperBob2 wrote: post #140

Earlier quoted context omitted.

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.

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

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

#146

Post by kasabali »

delta_p_delta_x wrote: post #31
Maken wrote: post #8

Earlier quoted context omitted.

XP is Microsoft's prettiest OS by far.

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.

IMO Aero parts looked phenomenal but older Win32 parts like toolbars etc. didn't fit and looked odd

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

#147

Post by kevin_thibedeau »

cabirum wrote: post #107
mawadev wrote: post #20

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…

Counterexample: desktop icon layout in quadratic time: https://randomascii.wordpress.com/2021/02/16/arranging-invis... Its not like windows is the pinnacle of software craftsmanship.

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.

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

#148

Post by kevin_thibedeau »

VCFundedGenYer wrote: post #124
sph wrote: post #73

Earlier quoted context omitted.

It'll pop up elsewhere so might as well keep it online on their servers. And it's an old version of the OS anyway. If it were the Windows 11 source, it'd get nuked immediately

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

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

#149

Post by adrianmonk »

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

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

#150

Post by sunaookami »

Maken wrote: post #24
sunaookami wrote: post #22

Earlier quoted context omitted.

You mean 7 ;)

Windows 7 fixed Vista a bit, but the Aero windows were never pretty and the non-Aero decorations were painfully obvious a placeholder.

Aero was pretty though.
Post reply on HN