• The Old New Thing

    Raymond, why did you stop studying Chinese? It has no grammar!


    One of my colleagues, a native Chinese speaker, asked me whether I was still learning Mandarin Chinese. I told him that I had given up. He was baffled by this.

    "But Chinese is such a simple language. It has no grammar!"

    Now of course, Mandarin has a grammar, because every language has a grammar.

    This is one of the curses of being a native speaker of a language: You don't even realize how hard your language is. As far as you're concerned, your native language is as easy as falling off a log.¹

    Now, it's true that Mandarin has almost no inflections, unlike most European languages. But that's not the same as saying it has no grammar. It's just that the grammar moves from being internal (inflection) to external (helping words and word order).

    Sidebar: David from Popehat lays out some of the simplifications, but I think he oversimplifies the use of the completion marker 了. It's not strictly speaking a past-tense marker, at least not in the sense we consider it in English. Proper use of 了 is more complicated, and this page tries to explain some of the subtleties. David later tries to explain Mandarin phonology. I must admit that I have an advantage in already having a tonal language wired into my brain, so I don't have the hurdle of learning to hear and speak tones. I just have to learn to hear and speak different tones. Which is still frustrating. End sidebar

    One of the consequences of "your own native language is simple" is that native speakers are sometimes the worst choices for explaining their own language, since they simply fail to recognize how weird their language is. An example I gave some time ago was that elusive third tone. If you ask a native speaker how it is pronounced, they will say one thing ("dipping tone"), but then when they themselves speak the third tone they do something completely different ("low level tone"). Native speakers are so convinced that the third tone dips that when you call them on it, they insist that the tone dipped, when in fact it barely moved at all.

    That conversation with my father went something like this.

    Me: "In that sentence, you said ⟨low level tone⟩."

    My father: "No, I didn't. I said ⟨dipping tone⟩."

    Me: "Well, sure, that time you said ⟨dipping tone⟩. But in the original sentence, you said ⟨low level tone⟩."

    My father: "No, I didn't. Listen again. ⟨repeats sentence and uses low level tone⟩."

    Me: "There, see? You used ⟨low level tone⟩."

    My father: "No, I didn't. Here, you repeat back to me what you think I said."

    Me: "⟨says sentence with low level tone⟩."

    My father: "There, you got it!"

    Me: "But I used the wrong tone! I should have said, ⟨says sentence with dipping tone⟩."

    My father: "No, that's wrong. You exaggerated the tone too much."

    That last remark from my father was what made it click for me: The low level tone and the dipping tone are complementary allophones. (My father, of course, has no idea what a complementary allophone is, but that's okay.)

    Another example of native speakers not seeing the complexity in their own language is the use of the negative adverb 没. Mandarin has two main adverbs that mean "not": 不 and 没. If you ask a native speaker, they will tell you, "It's very simple. 不 is the general-purpose negation, and 没 is used only to negate the verb to have. In other words, 没 is always followed by 有." But then you will see that native speakers use 没 to negate all sorts of things that aren't 有. If you point this out, they will retcon it by saying that the phrase 没關係 ("no connection", which is an idiom that means "it doesn't matter, don't worry about it") is really a shorthand for 没有關係 ("doesn't have a connection"). Native speakers play this card whenever an out-of-place 没 shows up. "Oh, it's negating an invisible 有." If you ask them how to tell when there is an invisible 有 in a sentence, they will say "You just have to know," or sometimes the circular "Stick a 没 in front and see if it makes sense."

    Sidebar: Here's a page that tries to explain the difference between 不 and 没. The way I internalize it based on limited observation is to say that 不 is not tied to a moment in time (innate or habitual property), whereas 没 refers to a particular incident (momentary property).

    doesn't get wet
    (it's water-resistant)
    isn't wet
    (he has an umbrella)
    doesn't drink milk
    (he's lactose intolerant)
    isn't drinking milk
    (he chose water)

    This is similar to the distinction between English simple ("I do") and progressive ("I am doing"). Furthermore, 没 carries a sense of "yet"; you are denying that something is true now, but expecting that to change in the future. End sidebar

    One downside about having such a superficially simple grammar is that it makes the language much more ambiguous. The more complex grammar of European languages acts as a checksum. If I say, "He are coming," then you know that something went wrong. The grammatical doodads act like signposts to confirm that you the listener are parsing the sentence correctly. It's like the road sign after every highway exit that reassures you, "You are still on Highway 405 Northbound." One of my colleagues told me that he missed those signs on his trip to Italy. There would be signs labeling each exit, but rarely was there a sign telling you what highway you were currently on!

    To me, Chinese is difficult to learn because of its lack of guideposts that help steer you onto the right track. Without them, many sentences end up ambiguous. (In that example, the lack of any grammatical particle that distinguishes imperative from declarative mood led to the confusion.) The relative scarcity of grammatical particles makes me feel like I'm talking baby-talk. "Me want eat cookie."²

    Resolving ambiguity is made even harder by the fact that every word in Mandarin has about a dozen homophones (fortunately, most of them not used in everyday speech), so you aren't even sure what word you're dealing with at the moment you hear it. You just know it's one of these two or three, and you have to wait and see which one actually makes sense when combined with the other words in the sentence (some of which may themselves also be ambiguous).

    Adding to the ambiguity is that in many cases, you can omit words from a sentence if they are implied from context. So you now have to juggle the ambiguous mapping of sounds to words, the ambiguous grammatical context of those words (was that a statement or a direct order?), and choosing which implied words to insert to support your conclusion! Of course, native speakers can resolve all of these ambiguities very quickly, having been doing so since birth, and they are much better at picking up other cues (such as where the speaker speeds up and slows down) to help steer toward the correct interpretation. Indeed, in the language I learned as a young child, I can resolve these ambiguities with no difficulty at all.

    Sidebar: Even native speakers sometimes have to go into explicit ambiguity-resolution mode by adding clarifying context. This happens in English occasionally: You might say, "He had a bat (the animal)" because the shorter sentence "He had a bat" would be ambiguous. Did he have an animal or an instrument for striking? End sidebar

    One thing I do like to quibble about is the treatment of classifiers in Mandarin. Most people treat them as a quirk of the language, making them sound like an oddball feature that doesn't exist in European languages. An analogue in English would be the word "pair" when applied to scissors or pants. You can't say "a scissors" or "a pants"; you have to say "a pair of scissors" or "a pair of pants." (Particularly confusing because a "pair" of scissors or pants is still one article.) In Mandarin, every noun has a corresponding classifier.

    You can think of classifiers as the Mandarin version of grammatical gender. The nouns in the language fall into around 170 different categories, and you just have to know which category word goes with each noun. There are patterns that help the learning process, but there are always exceptions that you simply must memorize.

    For example, 条 is generally used for long, thin, flexible things, like a fish or a ribbon. But you also use it for dogs. Oh, and also for skirts and dresses. Go figure.

    So the next time a native Mandarin speaker complains that English has all these arbitrary rules that serve no purpose other than making the language harder to learn, just ask them about classifiers. (They will naturally defend classifiers by saying that they are completely obvious and in no way arbitrary.)

    Anyway, the bit about classifiers explains why the subway ticket vending machine asks you how many "sheets" you want: In Mandarin, it is very common to omit the noun and use only the classifier when the noun is implied from context. This happens in English, too. If you are a shop that repairs scissors, the clerk might ask, "What's wrong with this pair?" as shorthand for "What's wrong with this pair of scissors?"

    The classifier word for ticket is 張 which translates as sheet. The full question is "How many sheets of tickets?" But since you are at a ticket vending machine, the noun is implied from context, and the shorter sentence "How many sheets?" is used instead.

    ¹ This natural tendency to think of what you do as normal reveals itself in the words that the Chinese language uses to refer to itself. The name for the country of China is 中國, which translates as the middle kingdom, because by an amazing coincidence, China happens to be right in the middle of the map. And the name for the language itself is 普通話, which translates as normal speech, because we all talk normally; it's the foreigners who talk funny by using their own words for everything.³

    ² In practice, the distinction between baby-talk and adult-talk in Chinese is accomplished in two ways. First, babies have a specialized vocabulary: babies say doggy instead of dog, for example. Second, adults employ modal particles which convey the attitude of the speaker. Cantonese is notorious for having a large number of these sorts of particles. I don't know most of them, so my speech tends to come off as rather rude and abrupt.

    ³ Someone said that a neighbor of his grandmother complained, "I don't understand why people in foreign countries bother to learn a second language. Why don't they just talk normal?"

  • The Old New Thing

    How do I get a handle to the primary monitor?


    There are various ways of getting a monitor. You can get the monitor from a point, from a rectangle, or from a window. But how do you get the primary monitor?

    The primary monitor is defined to be the one which has (0, 0) as its origin. Therefore, one solution is

    HMONITOR GetPrimaryMonitor()
     POINT ptZero = { 0, 0 };
     return MonitorFromPoint(ptZero,

    The desktop window by convention is deemed to reside primarily on the primary monitor, so you could also use this:

    HMONITOR GetPrimaryMonitor()
     return MonitorFromWindow(GetDesktopWindow(),

    Or you could just pass the null window handle. This is technically an illegal parameter, but by specifying MONITOR_DEFAULT­TO­PRIMARY, you are saying, "If anything goes wrong, give me the primary monitor."

    HMONITOR GetPrimaryMonitor()
     return MonitorFromWindow(nullptr,

    In this case, we are intentionally going astray because we want to kick in the MONITOR_DEFAULT­TO­PRIMARY behavior.

  • The Old New Thing

    Passing the incorrect object type for a handle, how bad is it?


    A customer asked a somewhat strange question: "We are calling Set­Event but passing the handle to a waitable timer. Application Verifier reports, "Incorrect object type for handle." But the code works well. We want to know the risks of passing the wrong object type to Set­Event. Is the recommendation only to pass handles of type "Event" to Set­Event?

    Let's answer those questions in reverse order.

    Yes, the recommendation is only to pass handles of type "Event" to Set­Event, just as the recommendation is only to pass handles of type "Semaphore" to Release­Semaphore, and more generally, only to pass valid parameters to functions.

    What is the risk of passing the wrong object type? You're lucky that the kernel does object type validation before proceeding, so your error is caught during parameter validation and the function fails with the error ERROR_INVALID_HANDLE (or status code STATUS_OBJECT_TYPE_MISMATCH, if the function returns status codes instead of error codes).

    Of course, if you are encountering this problem only because you are using a handle after closing it (and then the handle got recycled as a timer handle), then you merely got lucky. Maybe tomorrow you won't be so lucky, and the handle will get recycled as another unrelated event. Tomorrow, your Set­Event call will succeed and set some other guy's event. This will probably cause that other guy to get really confused. "This event is set when the modulator has finished calibrating. But the event is getting signaled before the calibration is complete, so my code ends up using an uncalibrated modulator! I set a breakpoint on my Set­Event call, and it never fires, yet the event is set. Help me debug this. I've spent a week trying to figure out what's wrong!"

    As to the final remark, "But the code works well," it's not clear what the customer meant by that. What does "works well" mean in this context? Do they mean, "The event is successfully set even though it's not an event"? How can you successfully perform an event operation on something that isn't an event? Or perhaps they mean, "Our code seems to work okay in spite of this mistake." The operative phrase there is "seems to". It may seem to work well, but someday it won't, and at the most inconvenient time.

  • The Old New Thing

    Microspeak: Line of sight


    I first encountered this term in a meeting I attended.

    Q: We would like to be able to reverse the polarity of the neutron flow without requiring a reboot.

    A: Yes, that is something we've been thinking about, but we don't have line of sight to having that feature before the end of the month.

    From context, having line of sight to a result means something like "Have made it part of our immediate plans to achieve that result."

    This appears to be extending the idiom on the horizon. Literally, something on the horizon. is at the edge of what can be seen. Figuratively, then, something that is on the horizon is at the edge of what can be predicted. And if something can be seen, then you have line of sight to it.

    There is another aspect of line of sight: The view to the object must be unobstructed. Taking the analogy further, then, having line of sight to a result means that there is a plan for achieving that result that is not dependent on work from another team.

    Note that I don't know if the "unobstructed" part of the analogy was intended by the speaker. All I have to work from is that one snippet of conversation.

    In an attempt to obtain better insight into the phrase line of sight, I searched the intranet, and the hits fell into a few categories.

    One category was people using the term literally, usually in the context of wireless communications.

    Another category appeared to use the phrase as a synonym for "insight obtained from information":

    Monthly tear sheets are improving line of sight.
    Teams were empowered to reallocate expenses within discretionary line items, but there was a lack of transparency into these changes. Forecasting was a challenge because we did not have line of sight into these reallocation decisions. We will address this by developing a pivot tool that provides management a consolidated line of sight into spend by resource.

    Note also the business jargony use of spend as a noun, meaning expenditure.

    The third category appears to be what I heard in that meeting, where it means something like "a path to a result":

    XYZ was impacted by ABC and DEF. We have line of sight to get back on track.

    And then I think I hit the jackpot: Somebody defined the term, sort of.

    Line of sight to ending year $XX under budget

    XYZ is at 99% pass, with line of sight to ending the year at 100% pass. ABC is $YY under budget, and is on track to end the year at $XX under budget.

    The value $XX was repeated both in the heading and in the body, which let me match the two statements. And one of the statements uses the phrase line of sight, whereas the other uses the more conventional phrase on track.

    I therefore conclude that the two are roughly synonyms. Line of sight to X means on track to X.

    Though this means that one of the citations above translates to "We are on track to get back on track," which sounds kind of eerily meta.

    The preferred emphatic form of line of sight appears to be clear line of sight.

  • The Old New Thing

    Applying a filter to the contents of an Explorer Browser


    Today's Little Program hosts an Explorer Browser but filters the contents to remove DLL files. You can, of course, substitute your own filter. (For example, maybe you want to show only files that changed since the last time the user ran your program, or you might want a view of My Computer but filtered to show only removable drives.)

    Remember that Little Programs do little to no error checking, and they don't necessarily demonstrate the best programming style. They're just quick demonstrations. Today's smart pointer library is… (rolls dice) … WRL!

    Start with our minimal explorer browser program and make these changes.

    #include <shlwapi.h> // PathFindExtensionW
    #include <wrl\client.h>
    #include <wrl\implements.h>
    using namespace Microsoft::WRL;
    class FolderFilterNoDLLs :
        public RuntimeClass<RuntimeClassFlags<ClassicCom>,
     // *** IFolderFilter ***
     IFACEMETHODIMP GetEnumFlags(IShellFolder *psf,
        PCIDLIST_ABSOLUTE pidlFolder, HWND *phwnd,
        DWORD *pgrfFlags) { return S_OK; }
     IFACEMETHODIMP ShouldShow(IShellFolder *psf,
        PCIDLIST_ABSOLUTE pidlFolder,
        PCUITEMID_CHILD pidlItem)
      BOOL fShow = TRUE;
      ComPtr<IShellItem> spsi;
      HRESULT hr = SHCreateItemWithParent(pidlFolder, psf, pidlItem,
      if (SUCCEEDED(hr)) {
       SFGAOF sfgaof;
       hr = spsi->GetAttributes(SFGAO_FILESYSTEM | SFGAO_FOLDER,
       if (SUCCEEDED(hr) && sfgaof == SFGAO_FILESYSTEM) {
        LPWSTR pszName;
        hr = spsi->GetDisplayName(SIGDN_PARENTRELATIVEPARSING,
        if (SUCCEEDED(hr))
         fShow = CompareStringOrdinal(
                     PathFindExtensionW(pszName), -1,
                     L".dll", -1, TRUE) != CSTR_EQUAL;
      if (SUCCEEDED(hr)) hr = fShow ? S_OK : S_FALSE;
      return hr;

    The real work happens in the Should­Show method.

    • Create an IShellItem because it's more convenient.
    • Query the SFGAO_FILE­SYSTEM and SFGAO_FOLDER attributes.
    • If the attributes say "Yes, it's a file system object, and no, it's not a folder"...
      • Get the display name.
      • If the display name ends in .dll, then hide the item.

    All that's left is to plug this into the Explorer Browser.

    OnCreate(HWND hwnd, LPCREATESTRUCT lpcs)
        BOOL fSuccess = FALSE;
        RECT rc;
        ComPtr<IFolderFilter> spff;
        ComPtr<IFolderFilterSite> spffs;
        if (SUCCEEDED(CoCreateInstance(CLSID_ExplorerBrowser, NULL,
                             CLSCTX_INPROC, IID_PPV_ARGS(&g_peb))) &&
            GetClientRect(hwnd, &rc) &&
            SUCCEEDED(g_peb->Initialize(hwnd, &rc, NULL)) &&
            SUCCEEDED(g_peb->SetOptions(EBO_NAVIGATEONCE)) &&
            SUCCEEDED(MakeAndInitialize<FolderFilterNoDLLs>(&spff)) &&
            SUCCEEDED(g_peb->QueryInterface(IID_PPV_ARGS(&spffs))) &&
            SUCCEEDED(spffs->SetFilter(spff.Get())) &&
                             L"C:\\Program Files\\Internet Explorer",
                                            NULL, &pidl, 0, NULL)) &&
            SUCCEEDED(g_peb->BrowseToIDList(pidl, SBSP_ABSOLUTE))) {
            fSuccess = TRUE;
        return fSuccess;

    We apply the filter to the IExplorerBrowser by querying for IFolder­Filter­Site and using IFolder­Filter­Site::Set­Filter to attach our "no DLLs" filter.

    Bonus reading: Filtering the folders that appear in the Browse for Folder dialog.

  • The Old New Thing

    The case of the file that won't copy because of an Invalid Handle error message


    A customer reported that they had a file that was "haunted" on their machine: Explorer was unable to copy the file. If you did a copy/paste, the copy dialog displayed an error.

    1 Interrupted Action

    Invalid file handle

    ⚿  Contract Proposal
    Size: 110 KB
    Date modified: 10/31/2013 7:00 AM

    Okay, time to roll up your sleeves and get to work. This investigation took several hours, but you'll be able to read it in ten minutes because I'm deleting all the dead ends and red herrings, and because I'm skipping over a lot of horrible grunt work, like tracing a variable in memory backward in time to see where it came from.¹

    The Invalid file handle error was most likely coming from the error code ERROR_INVALID_HANDLE. Some tracing of handle operations showed that a call to Get­File­Information­By­Handle was being passed INVALID_FILE_HANDLE as the file handle, and as you might expect, that results in the invalid handle error code.

    Okay, but why was Explorer's file copying code getting confused and trying to get information from an invalid handle?

    Code inspection showed that the handle in question is normally set to a valid handle during the file copying operation. So the new question is, "Why wasn't this variable set to a valid handle?"

    Debugging why something didn't happen is harder than debugging why it did happen, because you can't set a breakpoint of the form "Break when X doesn't happen." Instead you have to set a breakpoint in the code that you're pretty sure is being executed, then trace forward to see where execution strays from the intended path.

    The heavy lifting of the file copy is done by the Copy­File2 function. Explorer uses the Copy­File2­Progress­Routine callback to get information about the copy operation. In particular, it gets a handle to the destination file by making a duplicate of the hDestination­File in the COPY­FILE2_MESSAGE structure. The question is now, "Why wasn't Explorer told about the destination file that was the destination of the file copy?"

    Tracing through the file copy operation showed that the file copy operation actually failed because the destination file already exists. The failure would normally be reported as ERROR_FILE_EXISTS, and the offending Get­File­Information­By­Handle would never have taken place. Somehow the file copy was being treated as having succeeded even though it failed. That's why we're using an invalid handle.

    The Copy­File2 function goes roughly like this:

    HRESULT CopyFile2()
     BOOL fSuccess = FALSE;
     HANDLE hSource = OpenTheSourceFile(); // calls SetLastError() on failure
     if (hSource != INVALID_HANDLE_VALUE)
      HANDLE hDest = CreateTheDestinationFile(); // calls SetLastError() on failure
      if (m_hDest != INVALID_HANDLE_VALUE)
       if (CopyTheStuff(hSource, hDest)) // calls SetLastError() on failure
        fSuccess = TRUE;
     return fSuccess ? S_OK : HRESULT_FROM_WIN32(GetLastError());

    Note: This is not the actual code, so don't go whining about the coding style or the inefficiencies. But it gets the point across for the purpose of this story.

    The Create­The­Destination­File function failed because the file already existed, and it called Set­Last­Error to set the error code to ERROR_FILE_EXISTS, expecting the error code to be picked up when it returned to the Copy­File2 function.

    On the way out, the Copy­File2 function makes two calls to Close­Handle. Close­Handle on a valid handle is not supposed to modify the thread error state, but somehow stepping over the Close­Handle call showed that the error code set by Create­The­Destination­File was being reset back to ERROR_SUCCESS. (Mind you, this was a poor design on the part of the Copy­File2 function to leave the error code lying around for an extended period, since the error code is highly volatile, and you would be best served to get it while it's still there.)

    Closer inspection showed that the Close­Handle function had been hooked by some random DLL that had been injected into Explorer.

    The hook function was somewhat complicated (more time spent trying to reverse-engineer the hook function), but in simplified form, it went something like this:

    BOOL Hook_CloseHandle(HANDLE h)
     HookState *state = (HookState*)TlsGetValue(g_tlsHookState);
     if (!state || !state->someCrazyFlag) {
      return Original_CloseHandle(h);
     ... crazy code that runs if the flag is set ...

    Whatever that crazy flag was for, it wasn't set on the current thread, so the intent of the hook was to have no effect in that case.

    But it did have an effect.

    The Tls­Get­Value function modifies the thread error state, even on success. Specifically, if it successfully retrieves the thread local storage, it sets the thread error state to ERROR_SUCCESS.

    Okay, now you can put the pieces together.

    • The file copy failed because the destination already exists.
    • The Create­The­Destination­File function called Set­Last­Error(ERROR_FILE_EXISTS).
    • The file copy function did some cleaning up before retrieving the error code.
    • The cleanup functions are not expected to alter the thread error state.
    • But the cleanup function had been patched by a rogue DLL, and the hook function did alter the thread error state.
    • This alteration caused the file copy function to think that the file was successfully copied even though it wasn't.
    • In particular, the caller of the file copy function expects to have received a handle to the copy during one of the copy callbacks, but the callback never occurred because the file was never copied.
    • The variable that holds the handle therefore remains uninitialized.
    • This generates an invalid handle error when the code tries to use that handle.
    • This error is shown to the user.

    An injected DLL that patched a system call resulted in Explorer looking like an idiot. (As Alex and Gaurav well know, Explorer is perfectly capable of looking like an idiot without any help.)

    We were quite fortunate that the error manifested itself as a failure to copy the file. Imagine if Explorer didn't use Get­File­Information­By­Handle to get information about the file that was copied. The Copy­File2 function returns S_OK even though it actually failed and no file was copied. Explorer would have happily reported, "Congratulations, your file was copied successfully!"

    Stop and think about that for a second.

    A rogue DLL injected into Explorer patches a system call incorrectly and ends up causing all calls to Copy­File2 to report success even if they failed. The user then deletes the original, thinking that the file was safely at the destination, then later discovers that, oops, looks like the file was not copied after all. Sorry, it looks like that rogue DLL (which I'm sure had the best of intentions) had a subtle bug that caused you to lose all your data.

    This is why, as a general rule, Windows considers DLL injection and API hooking to be unsupported. If you hook an API, you not only have to emulate all the documented behavior, you also have to emulate all the undocumented behavior that applications unwittingly rely on.

    (Yes, we contacted the vendor of the rogue DLL. Ideally, they would get rid of their crazy DLL injection and API hooking because, y'know, unsupported. But my guess is that they are going to stick with it. At least we can try to get them to fix their bug.)

    ¹ To do this, you identify the variable and set a breakpoint when that variable is allocated. (This can be tricky if the variable belongs to a class with hundreds of instances; you have to set the breakpoint on the correct instance!) When that breakpoint is hit, you set a write breakpoint on the variable, then resume execution. Then you hope that the breakpoint gets hit. When it does, you can see who set the value. "Oh, the value was copied from that other variable." Now you repeat the exercise with that other variable, and so on. This is very time-consuming but largely uninteresting so I've skipped over it.

  • The Old New Thing

    Why is the FAT driver called FASTFAT? Why would anybody ever write SLOWFAT?


    Anon is interested in why the FAT driver is called FASTFAT.SYS. "Was there an earlier slower FAT driver? What could you possibly get so wrong with a FAT implementation that it needed to be chucked out?"

    The old FAT driver probably had a boring name like, um, FAT.SYS. At some point, somebody decided to write a newer, faster one, so they called it FASTFAT. And the name stuck.

    As for what you could possibly get so wrong with a FAT implementation that it needed to be improved: Remember that circumstances change over time. A design that works well under one set of conditions may start to buckle when placed under alternate conditions. It's not that the old implementation was wrong; it's just that conditions have changed, and the new implementation is better for the new conditions.

    For example, back in the old days, there were three versions of FAT: FAT8, FAT12, and FAT16. For such small disks, simple algorithms work just fine. In fact, they're preferable because a simple algorithm is easy to get right and is easier to debug. It also typically takes up a lot less space, and memory was at a premium in the old days. An O(n) algorithm is not a big deal if n never gets very large and the constants are small. Since FAT16 capped out at 65535 clusters per drive, there was a built-in limit on how big n could get. If a typical directory has only a few dozen files in it, then a linear scan is just fine.

    It's natural to choose algorithms that map directly to the on-disk data structures. (Remember, data structures determine algorithms.) FAT directories are just unsorted arrays of file names, so a simple directory searching function would just read through the directory one entry at a time until it found the matching file. Finding a free cluster is just a memory scan looking for a 0 in the allocation table. Memory management was simple: Don't try. Let the disk cache do it.

    These simple algorithms worked fine until FAT32 showed up and bumped n sky high. But fortunately, by the time that happened, computers were also faster and had more memory available, so you had more room to be ambitious.

    The big gains in FASTFAT came from algorithmic changes. For example, the on-disk data structures are transformed into more efficient in-memory data structures and cached. The first time you look in a directory, you need to do a linear search to collect all the file names, but if you cache them in a faster data structure (say, a hash table), subsequent accesses to the directory become much faster. And since computers now have more memory available, you can afford to keep a cache of directory entries around, as opposed to the old days where memory was tighter and large caches were a big no-no.

    (I wonder if any non-Microsoft FAT drivers do this sort of optimization, or whether they just do the obvious thing and use the disk data structures as memory data structures.)

    The original FAT driver was very good at solving the problem it was given, while staying within the limitations it was forced to operate under. It's just that over time, the problem changed, and the old solutions didn't hold up well any more. I guess it's a matter of interpretation whether this means that the old driver was "so wrong." If your child outgrows his toddler bed, does that mean the toddler bed was a horrible mistake?

  • The Old New Thing

    The contents of the Start page are not programmatically accessible


    A customer wanted to know if is possible for an application to edit the user's Start page.

    No, there is no interface for editing the user's Start page or even knowing what is on it. The Start page is the user's personal space and applications should not be messing with it.

    Imagine if it were possible. Every application would edit the Start page to put themselves at the front!

    It turns out that the customer wanted their application to make some changes to the user's Start page when it was installed. Specifically, they wanted to hunt down tiles belonging to their competitors and delete them, then insert a tile for the newly-installed program in exactly the spot the competitor's tile used to be.

    In other words, somebody was looking to get a really nice bonus.

  • The Old New Thing

    A question about preventing the system from going to the idle state turns out to be misguided


    A customer asked how they could have their program prevent the system from going to the idle state. Specifically, when the system goes idle, the application gets into a weird state where it starts leaking memory like crazy. The program normally uses around 100MB of memory, but when the system goes idle, something funky happens and the program's memory usage shoots up to 4GB. To avoid this problem, they want to prevent the system from entering the idle state.

    Now, if your application is a special-purpose program running on a dedicated computer, then blocking the entry into the idle state might be acceptable. After all, the user bought the computer specifically to run your program and nothing else. But the description of the program provided by the customer did not suggest that this was the case. It was just some program being developed for a general audience.

    Interfering with the functioning of the entire system to hide a bug in your application is a horrible thing to do. It means that when your program is running, idle-time tasks never run, the computer never enters a low-power state, laptop batteries drain ten times faster than normal, and you basically ruin the entire computer.

    What you should do is debug your program and fix the memory leak.

    This is like saying, "We manufacture car stereo systems, and we found that when the car is coasting, the power from the alternator is not sufficient to drive the speakers. We would like to prevent the car from coasting."

  • The Old New Thing

    Enumerating the ways of distributing n balls into k boxes


    Suppose you had n indistinguishable balls and k distinguishable boxes. Enumerate the ways of distributing the balls into boxes. Some boxes may be empty.

    We can represent each distribution in the form of n stars and k − 1 vertical lines. The stars represent balls, and the vertical lines divide the balls into boxes. For example, here are the possible distributions for n = 3, k = 3:


    This visualization is known in combinatorics circles as stars and bars.

    From this visualization, we see that what we are doing is taking n + k − 1 slots, and in each slot placing a star or a bar, subject to the constraint that there be n stars and k − 1 bars. Another way of looking at this is that we are choosing a subset of size k − 1 from a set of size n + k − 1 (the subset specifying where the bars go).

    Now we can fire up our subset-generating machine.

    function Distributions(n, k, f) {
     Subsets(n + k - 1, k - 1, function(s) {
      s.push(n + k);
      f(s.map(function(v, i) { return v - (s[i-1]||0) - 1; }));

    We ask to generate subsets of size k − 1 from a set of size n + k − 1. For each such subset, we draw an artificial bar at the end (slot n + k), then calculate the number of stars between the bars. The number of stars between two bars is the distance between the two bars, minus 1 because the bar takes up space, too.

    Another solution is to reduce this to a problem we already know how to solve: enumerating integer compositions. After distributing the balls into boxes, we go around like Santa Claus and give each box one extra ball, which produces a composition. Conversely, for any composition, remove one ball from each box, and you get a distribution.

    function Distributions(n, k, f)
     Compositions(n + k, k, function(s) {
      f(s.map(function(v) { return v - 1; }));

    We added k extra balls, so we need to generate compositions of n + k. When we get each composition, we take one ball away from each box and call that the distribution.

Page 7 of 441 (4,405 items) «56789»