This particular emulator employed binary translation, generating native code to perform the equivalent operations of the original x86-32 code. This offered a significant performance improvement over emulation via interpreter. You can imagine that x86-32 is just a bytecode, and the emulator is a JIT compiler.

Anyway, my colleague found that there was one program that needed to allocate around 64KB of memory on the stack and initialize it. The standard way of doing this is to perform a stack probe to ensure that 64KB of memory is available, then subtracting 65536 from the stack pointer, and then initializing the memory in a small, tight loop.

But using a loop to initialize the memory was too mundane for whatever compiler was used to compile this code. Instead of generating a loop to initialize each byte of the buffer, the compiler “optimized” the code by unrolling the loop into 65,536 individual “write byte to memory” instructions, each 4 bytes long.

All in all, it took this program 256 kilobytes of code to initialize 64 kilobytes of data.

This offended the team so much that they added special code to the translator to detect this horrible function and replace it with the equivalent tight loop.

The post The time the x86 emulator team found code so bad that they fixed it during emulation appeared first on The Old New Thing.

To avoid clogging the receiving thread, the customer queued a work item to the thread pool to process the data that was just received. However, they found that sometimes, the work item doesn’t run immediately but rather has a 100ms latency. But their program needs to process the data within 20ms. Is there a way to set a deadline on a thread pool work item, so that the system will make sure that it runs before a certain period of time elapses?

As I’ve noted before, the thread pool is designed for throughput, not latency. There is no option to set a deadline on a work item.

One reason why the thread pool is being slow to dispatch the work items is that there are other unrelated work items in the thread pool, and those other tasks are competing with your data processing task for the thread pool’s attention. On top of that, some of those other tasks might be long-running, which takes a thread pool thread out of commission for an extended period.

You can take these conflicting work items out of the picture by creating your own custom thread pool: Call Create­Thread­Pool and queue your work to that thread pool (by setting that thread pool in the work item’s environment). Now you won’t have any competing work items getting in front of you in the thread pool work queue because those competing work items are going to the process default thread pool and not to your private thread pool.

Note however that even though your work items are no longer fighting with other work items for the attention of your private thread pool, those other work items are still running on the process default thread pool, so they are still competing against your work items for CPU. But at least your work item got dispatched.

I’m guessing that the order in which the batches are processed is important, so you should set your private thread pool’s maximum thread count to 1 so that you don’t start processing one batch of data until you finish processing the previous batch. This effectively serializes the work items, but that’s what you want if you intend to process the batches in order.

In the case where you have a single-minded thread pool, you can prepare everything ahead of time so that all you have to do in the callback itself is call SubmitThreadpoolWork on a pre-created reusable work item.

// One-time preparation
pool = CreateThreadpool();
if (!pool) ⟦ error ⟧

TP_CALLBACK_ENVIRON env;
InitializeThreadpoolEnvironment(&env);
SetThreadpoolCallbackPool(&env, pool);
work = CreateThreadpoolWork(ProcessData, nullptr, &env);
if (!work) ⟦ error ⟧

void Callback()
{
    ⟦ add data to data queue ⟧
    SubmitThreadpoolWork(work); // request another callback
}

If you step back and look at this, you might realize that all we did was create a worker thread, but one where we delegated all the bookkeeping to the thread pool. Also, this particular customer was writing code in C#, and the BCL doesn’t have built-in support for custom thread pools.

So if all we have is a worker thread, maybe we can just make a worker thread. Here’s a really simple one.

Queue<Data> queue = new Queue<Data>();

Data WaitForWork()
{
    while (true) {
        lock (queue) {
            if (queue.Count > 0) {
                return queue.Dequeue();
            }
            Monitor.Wait(queue);
        }
    }
}

void WorkerThread()
{
    Data data;
    while ((data = WaitForWork()) != null) {
        ⟦ process the data #&x27e7;
    }
}

void QueueWork(Data data)
{
    lock (queue) {
        queue.Enqueue(data);
        Monitor.Pulse(queue);
    }
}

void EndWork()
{
    QueueWork(null);
}

The worker thread waits for elements to show up in the queue, and once one appears, it dequeues it and does whatever processing you want. If the queued value is null, that means that the worker thread is no longer needed, and it exits.

You can do something similar in C++ with a std::queue and a condition variable.

The post How can I schedule work on a thread pool with low latency? appeared first on The Old New Thing.

• Keep routines short and simple.
• Don’t make calls into a user mode service to validate the process, thread, or image.
• Don’t make registry calls.
• Don’t make blocking and/or Interprocess Communication (IPC) function calls.
• Don’t synchronize with other threads because it can lead to reentrancy deadlocks.

So far so good. It seems that these callback functions need to operate quickly and cannot block. These are callbacks that are invoked when a process starts or exits, when a thread starts or exits, when a DLL or EXE is loaded or unloaded, and various other low-level events.

The various prohibitions above suggest that these callouts are called during the process creation/termination sequence, so if you take a long time to deal with them, you are slowing down the entire system. And the rather extreme requirements, like “Don’t make registry calls,” suggest that they might even be called while the system holds internal locks.

The list of best practices continues:

• Use System Worker Threads to queue work especially work involving:
  • Slow APIs or APIs that call into other process.
  • Any blocking behavior that could interrupt threads in core services.

Okay, so this is providing a suggestion on how you can offload expensive work to code running outside the callback. This once again highlights that the callback itself needs to be fast with minimal blocking.

My colleagues in enterprise support often run into cases where the reason for a system hang is a driver violating the rule that these callbacks must return quickly. For example, a common anti-pattern is a driver whose callback starts by following the guidance above to queue work to a System Worker Thread, but then they block until the work item completes.

This is a case of following the rules without understanding why the rules are there.

The rule is that the callback needs to be fast and return quickly. The driver followed the letter of the law by delegating the work to a System Worker Thread, and there’s no rule that says “Don’t wait for work items”, so they must have figured that this gave them a loophole for executing synchronous long-running work.

But the rules “Don’t make blocking and/or Interprocess Communication (IPC) function calls” and “Don’t synchronize with other threads because it can lead to reentrancy deadlocks” make it clear that you shouldn’t be blocking in your callback for extended periods of time. The “Don’t”s are just calling out some common ways that your callback can block.

And it looks like the documentation was updated in 2020 to call out this specific case:

• If you use System Worker Threads, don’t wait on the work to complete. Doing so defeats the purpose of queuing the work to be completed asynchronously.

One could argue that this rule is already covered by the “Don’t synchronize with other threads” rule, but I guess the driver vendor interpreted it as “But I’m not synchronizing with another thread. I’m synchronizing on an event!” But of course, the event is set by another thread, so you are effectively synchronizing with another thread.

My colleague in enterprise support describes this as the “It wasn’t me, it was my brother” excuse. You are told by your parents not to turn on the television set, so you tell your brother to do it. Technically, you didn’t turn the television set on, but in effect, you did because your brother is acting under your instructions. (This is why contracts often contain wording like “may not disclose or cause to be disclosed,” so that you can’t say “No, I totally didn’t disclose it. I gave the information to Bob, and it was Bob who disclosed it!”)

The documentation should open with something like this:

The callback function must perform its work quickly without blocking. If you need to do complex work or synchronize with other threads or processes, do the work asynchronously, such as by using System Worker Threads.

And then it can give a list of examples of things that count as blocking.

Some examples of blocking that is not allowed from the callback function:

And then it can follow up with additional constraints.

Furthermore, the callback function may not perform any of the following operations:

The post Understanding the rationale behind a rule when trying to circumvent it appeared first on The Old New Thing.

Let’s illustrate this with our scratch program.

POINT g_pt;
const RECT g_rcExclude = { 100, 100, 200, 200 };

RECT ItemRect(POINT pt)
{
    return RECT{ pt.x - 10, pt.y - 10, pt.x + 10, pt.y + 10 };
}

The g_pt variable holds the location of our object, and the g_rcExclude is the rectangle in which the object is forbidden. The ItemRect function produces a bounding rectangle for our object so we can draw something there.

void
PaintContent(HWND hwnd, PAINTSTRUCT* pps)
{
    FillRect(pps->hdc, &g_rcExclude, (HBRUSH)(COLOR_WINDOWTEXT + 1));
    RECT rcItem = ItemRect(g_pt);
    FillRect(pps->hdc, &rcItem, (HBRUSH)(COLOR_APPWORKSPACE + 1));
}

Painting our content is a straightforward matter of drawing the forbidden rectangle in the text color and drawing the object in the app workspace color.

void OnMouseMove(HWND hwnd, int x, int y, UINT keyFlags)
{
    POINT ptNew = { x, y };

    if (PtInRect(&g_rcExclude, ptNew)) {
        // Clamp to nearest legal position
        int leftMargin = ptNew.x - g_rcExclude.left;
        int topMargin = ptNew.y - g_rcExclude.top;
        int rightMargin = g_rcExclude.right - ptNew.x;
        int bottomMargin = g_rcExclude.bottom - ptNew.y;

        int dx, dy;
        int x, y;
        if (leftMargin < rightMargin) {
            x = g_rcExclude.left;
            dx = leftMargin;
        } else {
            x = g_rcExclude.right;
            dx = rightMargin;
        }
        if (topMargin < bottomMargin) {
            y = g_rcExclude.top;
            dy = topMargin;
        } else {
            y = g_rcExclude.bottom;
            dy = bottomMargin;
        }
        if (dx < dy) {
            ptNew.x = x;
        } else {
            ptNew.y = y;
        }
        POINT ptScreen = ptNew;
        ClientToScreen(hwnd, &ptScreen);
        SetCursorPos(ptScreen.x, ptScreen.y);
    }

    if (g_pt.x != ptNew.x || g_pt.y != ptNew.y) {
        RECT rcItem = ItemRect(g_pt);
        InvalidateRect(hwnd, &rcItem, TRUE);
        g_pt = ptNew;
        rcItem = ItemRect(g_pt);
        InvalidateRect(hwnd, &rcItem, TRUE);
    }
}

// Add to WndProc

        HANDLE_MSG(hwnd, WM_MOUSEMOVE, OnMouseMove);

When the mouse moves, we take the mouse position and see if it is in the forbidden rectangle. If so, we update the coordinates to the nearest legal position and move the mouse there with Set­Cursor­Pos.

Whether or not we had to update the coordinates, if the result produces a new location, then invalidate the object’s old location (so it will be erased at the next paint cycle), update the object position, and then invalidate the object’s new position (so it will be drawn at the next paint cycle).

When you run this program, you can try to move the mouse into the forbidden rectangle, but the program will shove the mouse back out. However, it flickers a lot bcause the mouse briefly enters the forbidden rectangle before it is expelled from it.

The customer saw that there is a Clip­Cursor function to constrain the mouse to remain inside a rectangle, but is there an inverse version that forces the mouse to remain outside a rectangle?

There is no such function, but that’s okay.

What you can do when the mouse is in an illegal position is just pretend that it’s in a legal position. Let the user move the mouse into a illegal position, but show the feedback at the nearest legal position, and if they drop the object, let it drop at the nearest legal position.

In the above program, that means we remove the call to Set­Cursor­Pos.

void OnMouseMove(HWND hwnd, int x, int y, UINT keyFlags)
{
    POINT ptNew = { x, y };

    if (PtInRect(&g_rcExclude, ptNew)) {
        // Clamp to nearest legal position
        int leftMargin = ptNew.x - g_rcExclude.left;
        int topMargin = ptNew.y - g_rcExclude.top;
        int rightMargin = g_rcExclude.right - ptNew.x;
        int bottomMargin = g_rcExclude.bottom - ptNew.y;

        int dx, dy;
        int x, y;
        if (leftMargin < rightMargin) {
            x = g_rcExclude.left;
            dx = leftMargin;
        } else {
            x = g_rcExclude.right;
            dx = rightMargin;
        }
        if (topMargin < bottomMargin) {
            y = g_rcExclude.top;
            dy = topMargin;
        } else {
            y = g_rcExclude.bottom;
            dy = bottomMargin;
        }
        if (dx < dy) {
            ptNew.x = x;
        } else {
            ptNew.y = y;
        }
        // POINT ptScreen = ptNew;              
        // ClientToScreen(hwnd, &ptScreen);     
        // SetCursorPos(ptScreen.x, ptScreen.y);
    }

    if (g_pt.x != ptNew.x || g_pt.y != ptNew.y) {
        RECT rcItem = ItemRect(g_pt);
        InvalidateRect(hwnd, &rcItem, TRUE);
        g_pt = ptNew;
        rcItem = ItemRect(g_pt);
        InvalidateRect(hwnd, &rcItem, TRUE);
    }
}

This time, we don’t try to punish you for moving the mouse into the forbidden rectangle. But the object won’t follow the mouse into a forbidden region.

The post What’s the opposite of <CODE>Clip­Cursor</CODE> that lets me <I>exclude</I> the cursor from a region? appeared first on The Old New Thing.

During the evening, an unofficial game arose in which people started exchanging their name tags with others whom they met. It also served as a fun little conversation starter: If you swapped name tags with someone and ended up with the tag for somebody you didn’t know, it wasn’t hard to find a mutual acquaintance who could track them down and introduce you.

At one point, the employee who was retelling the story was in a group talking with Bill Gates, who was among the few attendees still wearing their original name tags. Bill spotted that one of the other people in the group had a “Gary Kildall” name tag. I don’t know whether Gary Kildall was actually invited to the party, or that somebody just created a Gary Kildall name tag as a joke. But Bill saw the “Gary Kildall” name tag and eagerly swapped his name tag for it.

The post The Microsoft Company Party where everybody played name tag swap appeared first on The Old New Thing.

Reducing the number of rotations in the discontiguous swap problem from three to two also shows how the solution can be generalized to shuffling an arbitrary number of variable-sized blocks: Given k blocks, of total size n, you can shuffle them arbitrarily in at most kn swaps in constant space: Take the block that goes first and rotate it to the front, which takes n swaps. Then recurse on what’s left.

You can reduce the number of swaps by comparing the sizes of the block that goes first and the block that goes last and choose to swap the larger block to the corresponding extreme.

I guess you could use this for sorting, but it’s probably enough of a hassle that you’ll just take the penalty of allocating a second block of memory rather than trying to be clever and doing it in-place.

In online discussion of this article, I saw a number of people say, “You can do this with the XOR trick,” but I’m not sure what XOR trick they are referring to. If they are talking about using XOR to swap two integer variables without introducing a third variable, that’s a cute trick I don’t see how it helps with moving variable-sized blocks around. It also doesn’t help with swapping non-integers, since it’s not clear how your XOR two strings or two Widgets.

Another note is that my unit of accounting was the “swap”, but really I should be counting “assignments” because the cycle decomposition algorithm doesn’t use swaps. For the purpose of accounting, I’ve been counting a single assignment as half a swap, though depending on how expensive the move constructor is, a single assignment/construction might only cost a third of a swap.

Finally, a clarification on my description of the solution as “constant space without allocation”: Clearly any algorithm requires some space: space for the parameters, return address, any registers used by the code, and any local variables and temporaries. As long as the number and size of these things is bounded by a constant, this is considered a “constant space” algorithm. Note that the size of an element is not known to the generalized algorithm, but once you implement the algorithm for a concrete element type, the size becomes a constant.

My description of this as “without allocation” is a shorthand for “without requiring dynamic memory allocation (because the amount of memory needed is known at compile time).”

I have a soft spot for algorithms that run in constant space (where the constant is reasonably small) because they remove the need to worry about how to recover if there is a memory allocation failure.

The post Rotation revisited: Shuffling more than three blocks, and other small notes appeared first on The Old New Thing.

According to the blurb for the book,

The topics included in it are of utmost significance and are bound to provide incredible insights to students. Some of the diverse topics covered in this text address the varied branches that fall under this category. Those in search of information to further their knowledge will be greatly assisted by this textbook.

This sounds like a book report written by a student who didn’t read the book! Those sentences could be used to describe pretty much any textbook.

Indeed, I found nearly identical sentences in the blurb for Casting Handbook (Hannah Wells, editor).

The topics included in this book on casting are of utmost significance and bound to provide incredible insights to readers. Some of the diverse topics covered in this book address the varied branches that fall under this category. It will serve as a valuable source of reference for graduate and post graduate students.

And in Food Industry: Processes and Technologies (Kaden Hunt, editor):

This book is compiled in such a manner, that it will provide in-depth knowledge about the theory and practice of the workings of food industry. Some of the diverse topics covered in this text address the varied branches that fall under this category. This textbook, with its detailed analyses and data, will prove immensely beneficial to professionals and students involved in this area at various levels.

And in Nutrition and Metabolism: Processes and Technologies (Kaden Hunt, editor):

This book provides comprehensive insights into the field of nutrition and metabolism. It provides deep insights about this field. Some of the diverse topics covered in this text address the varied branches that fall under this category. Such selected concepts that redefine this subject have been presented in it. This book aims to shed light on some of the unexplored aspects of this field. It is meant for students who are looking for an elaborate reference text on nutrition and metabolism.

One more example: Material Science and Engineering (Emilio McMahon, editor)

The book aims to shed light on some of the unexplored aspects of materials science and engineering. It describes in detail the various concepts and theories of this field. The topics included in it are of utmost significance and bound to provide incredible insights to students. Some of the diverse topics covered in this book address the varied branches that fall under this category. This textbook is an essential guide for both graduates and post-graduates in this discipline.

The common thread is that all of these books are published by Larson and Keller. I guess they can’t be bothered to spend time crafting a blurb that suits the book, so they just use the same blurb template for all of their books.

¹ Rory Jaffe found that the book cover image it is an Alamy stock photo from 2013 with the title “Program code on a monitor.”

The post The back cover of <I>C++: The Programming Language</I> also raises questions not answered by the front cover appeared first on The Old New Thing.

The trick is realizing that the total number of elements is equal to the sum of the lengths of each of its cycles, and each of the initial elements belongs to a different cycle. Therefore, we can just keep rotating elements until the number of elements rotated is equal to the total. We don’t have to precalculate the number of cycles; we just let the counter tell us when we’re done.

auto a = std::distance(first, mid); // number of "A" elements
auto n = std::distance(first, last); // total elements
auto count = 0;
auto k = 0;

while (count < n) {
    // Rotate the elements in the cycle starting at k
    auto save = std::move(first[k]);
    auto i, next = k;
    while (i = next, next = (i + a) % n, next != k) {
        first[i] = std::move(first[next]);
        ++count;
    }
    first[i] = std::move(save);
    ++count;
}

The post Rotation revisited: Avoiding having to calculate the gcd when doing cycle decomposition appeared first on The Old New Thing.

The implementation in clang’s libcxx performs the minimum number of swaps, roughly n/2, where n is the total number of elements. It does so by viewing the rotation as a permutation and walking through each of the cycles.

For notational convenience, let a be |A| and n be |A| + |B| (the total number of elements). The number of cycles is gcd(a, b), and the k‘th cycle consists of the elements starting at first + k, and then stepping to the next element by moving forward another a elements, with wraparound, until you return back to the starting point.

For example, if you have |A| = 4 and |B| = 6, then the cycle that starts at A1 takes 4 steps forward to continues to B1; takes another 4 steps forward to B5; then takes 2 steps forward, wraps around, and then two more steps forward, landing on A3; then takes 4 steps forward to B3; and then takes 4 steps forward and wraps around to A1, which is the starting point.

There’s another cycle that starts at A2 and continues to B2, B6, A4, B4, then back to A2.

Now, we’ve been counting swaps, but a single-element rotation is not done as a sequence of swaps, but rather by picking up the first element, sliding all the other elements over, and then putting the original first element at the end. I’ve been informally calling an assignment “half of a swap”, though a swap is really a constructor, two assignments, and a destructor. But let’s stick with the “half a swap” accounting fiction.

The rotation algorithm goes like this:

auto a = std::distance(first, mid); // number of "A" elements
auto n = std::distance(first, last); // total elements
auto g = gcd(a, n); // number of cycles

for (auto k = 0; k < g; ++k) {
    // Rotate the elements in the cycle starting at k
    auto save = std::move(first[k]);
    auto i, next = k;
    while (i = next, next = (i + a) % n, next != k) {
        first[i] = std::move(first[next]);
    }
    first[i] = std::move(save);
}

For example, if rotating A1, A2, B1, B2, B3, B4, there are two cycles: A1, B1, B3; and A2, B2, B4. The elements within each cycle rotate one position.

And when you’re done with all the cycles, you’ve rotated the entire A and B blocks.

This performs n/2 swaps, which is the fewest swaps of all the algorithms we’ve looked at so far. However, it has terrible locality because the elements in the cycle are all spread out.

Calculating the greated common divisor of two numbers can be done in O(log n) steps via Euclid’s algorithm.

int gcd(int a, int b)
{
    do {
        auto r = a % b;
        a = b;
        b = r;
    } while (r);
    return a;
}

Commenter Brent thought that the cycle decomposition algorithm was obvious. Of course, the trick is the step they called “Repeat”. How many times do you repeat?

The clang libcxx algorithm calculates the number of repeats by taking the gcd. But there’s a trick so we don’t have to calculated it at all. We’ll look at that trick next time.

Bonus chatter: I think it’s interesting that of the three major implementations of the C++ standard library, each one uses a different rotation algorithm when given random-access iterators!

The post Rotation revisited: Cycle decomposition in clang’s libcxx appeared first on The Old New Thing.

As with all shocking discoveries, this one will shock disappoint you.

The discovery is that the gcc libstdc++ algorithm is the same as the forward-iterator algorithm!

Let’s run both algorithms on a problem where the two blocks are A1, A2, A3, B1, B2, B3, B4, B5. I’ll put the old forward iterator algorithm on top and the new gcc libstdc++ algorithm below.

We swap at first and mid, then advance both pointers. The two algorithms agree until first reaches the end of the original A block.

The old algorithm recurses in order to exchange A1, A2, A3 with B4, B4. This happens by exchanging A1 with B4 and A2 with B5.

The new algorithm just keeps swapping first with mid, which also exchanges A1 with B4 and A2 with B5.

The old algorithm now recurses to swap the A3 block with the A1+A2 block. And that’s what the new algorithm does, too.

So it’s the same algorithm, just with a different point of view. It’s another case of the geeky thrill of discovering that two things are really the same thing, just with different labels.

Now, the two algorithms are not identical. The new algorithm is symmetric and performs its swaps from right to left if the larger block is on the right. The old algorithm always operates from left to right.

But the similarity is striking.

Next time, we’ll look at how clang performs rotation by decomposing into cycles.

The post Rotation revisited: A shocking discovery about gcc’s unidirectional rotation algorithm appeared first on The Old New Thing.