it may help or may hurt predictability (depending on how much you move windows aorund), but I think it would look better if it used a "minimum motion" mechanism to decide on the layout - it looks pretty weird when windows interchange position going into the overlay - the window on the left flies to the right, the window on the right flies to the left.

I agree with Owen about minimizing the shuffling of windows.  But in addition I would say that the Overlay isn't likely to be the primary way to find a window.  Regardless of how the windows are placed, the user is going to have to hunt any time they have more than 4 or 5 windows open.

I would say that breadcrumbs or a panel are more likely to be the primary method of swapping programs.

The overlay is more useful when you can't remember which workspace something was on, and I think it will really come into its own when you can search for a running program and see just the windows you want:
http://live.gnome.org/GnomeShell/DesignerPlayground/HighlightWindowsOnSearch

myxiplx: this is way off topic for this bug report.

Sorry, I was trying to ask (badly) whether gnome-shell needs the window layout to be predictable, didn't mean to stray so far off.

A few more comments about the details of doing minimum motion, from an IRC discussion:

 A simple 'layout out by minimum motion algorithm is just to do it greedy - 
 find the window closet to the target position at the upper left, find the
 window out of the remaining closest to the "target position" at the upper-right
 (for 4 windows), continue...

 To break ties in a stable fashion, use the monitor sequence of the window
 (i.e. start time effectively) - See the initially_seen_sequence in the 
 AppUsage structure in shell-app-monitor.c - a method would have to be
 added to get it for a window.

Marking gnome-love for the fairly simple method described above - a lot more complexity might be needed here in the long term.

Not sure if this helps or is a distraction, but...

For the 4 window case you don't even need to approximate. There are only 24 possible layouts, and you can easily just calculate how much total motion would be involved in each of them, and go with whichever works best.

Even for 6 windows, with 720 layouts to try, this is probably still pretty much instantaneous, though at some point it obviously stops working. Although, the complexity isn't actually quite O(n!), because all maximized and minimized windows are interchangeable in terms of where they eventually end up, so you only end up with a pathological number of layouts to consider if the user has large numbers of visible overlapping windows.

*** Bug 589009 has been marked as a duplicate of this bug. ***

Created attachment 143641 [details] [review]
[workspaces] Use a stable minimum-motion placement for windows

Rather than having the mapping from window into "slots" (or
possible positions in the workspaces) be dependent on stacking
order, compute the minimum-motion which is a vector from one
top left corner to another.  This order won't change as long
as the window set and their positions stay fixed.

There are two minimum motion algorithims; one simply computes
all possible placements by permuting the window list, up to
a current maximum of 5 windows.  Past that (which also happens
to be the number where we switch to a grid), we use a "greedy"
algorithm which for each slot, finds the window with least motion
for that slot.

To break any ties, we use an internal integer in MetaWindow which
enumerates the order in which windows were created.

Comment on attachment 143641 [details] [review]
[workspaces] Use a stable minimum-motion placement for windows

>+// Used in _orderWindowsPermutations, 5! = 720 which is probably the highest we can go
>+const POSITIONING_PERMUTATIONS_MAX = 5;

5! = 120, not 720

>+     * @permutationIndex: An integer from [0, list.length!)

Both here and the "5!" above, it might be clearer to say "factorial(n)" rather than "n!", since if you're not expecting to see mathematical notation it looks like the author was just excited. (The half-open interval also looks like a typo, although writing it out in English is not at all an improvement...)

>+    _iteratePermutations: function(list, func) {

"_foreachPermutation"?

>+        xDelta = Math.abs((rect.x + rect.width / 2) - (slotX + slotWidth / 2));
>+        yDelta = Math.abs((rect.y + rect.height / 2) - (slotY + slotHeight / 2));
>+        distance = Math.sqrt(Math.pow(xDelta, 2) + Math.pow(yDelta, 2));

The abs()es are redundant since you're squaring the values. And isn't x*x generally assumed to be faster than pow(x,2)?

>+                let delta = this._computeWindowMotion(metaWindow, slot, slotAbsGeometry);
>+
>+                motion += delta;

Hm... given permutation A with deltas [1, 1, 1, 1, 10] and permutation B with deltas [3, 3, 3, 3, 3], this algorithm would prefer A. OTOH, if you computed the sum of the *squares* of the delta values, that would penalize large motions more heavily, biasing it towards solutions like B, where the total motion is slightly larger, but it's more evenly distributed among the windows, which is probably what we want. (qv "least squares fit" and related stuff in statistics)

(And this actually *saves* us some math, because "computing the square of delta" really means just removing the Math.sqrt call in _computeWindowMotion and calling the result delta_squared.)

>+                // Take a copy
>+                minimumMotionPermutation = permutation.concat();

I don't think you need to copy it?

>+    _orderWindowsByMotionAndStartup: function(windows, slots) {

Slightly tangential: we need to figure out what to do with minimized windows. One possibility would be to pick slots for them and then have them zoom into view (a la the windowManager.js map effect) already in that slot, while the other windows are moving into their slots. (And then reverse the effect when leaving the overview.) I guess we'd still want to pick their slots based on their unminimized position though, so that if you then selected a minimized window, there'd still be a minimum of motion when leaving the overview.

>+        windows = appMonitor.sort_windows_by_app_sequence(windows);

I was going to suggest that this should be

    windows.sort(function(w1, w2) { return w2.get_stable_sequence() - w1.get_stable_sequence(); });

but I see that's not what sort_windows_by_app_sequence does... and I'm not sure why. shell_app_monitor_sort_windows_by_app_sequence() does not seem to add anything useful on top of meta_window_get_stable_sequence(). (I'm guessing _get_stable_sequence() must just have been a late addition to the game?)

>+        let visibleWindowIndicies = [];

"Indices". (Or "Indexes")

Not sure how sophisticated we want to get with this, but a general observation - while avoiding testing all permutations is going to be hard if we want an exact olution - the "minimum motion" problem is very non-local and likely NP-complete - there's a a lot of locality in the "iterate through all permutations, compute the distance" that isn't being taken advantage of here. If we're iterating through:

 1 2 3 4
 1 2 4 3
 1 3 2 4
 1 3 4 2
 1 4 3 2
 1 4 2 3
 ...

Half the time we're just swapping the position of the last two elements, etc.

Doing the permutations recursively, would allow reusing a lot of the summing up.
Something like:

function score(window, position) {
}

function computeBestOrdering(windows, positions) {
    let thisWindow = windows[0];
    if (windows.length == 1)
        return [score(thisWindow, positions[0]), positions];

    let bestOrdering;
    let bestScore;
    let remainingWindows = windows.slice(1);
    for (let i = 0; i < positions.length; i++) {
        let thisScore = score(thisWindow, positions[i]);
        let remainingPositions = positions.slice(0).splice(i);
        let [score, ordering] = computeBestOrdering(remainingWindows, remainingPositions);
        score += thisScore;

        if (bestScore == null || score < bestScore) {
            bestScore = score;
            ordering.insert(0, positions[i]);
            bestOrdering = ordering;
        }
    }

    return bestScore, bestOrdering;
}

The above is not tested, and could be optimized further in a couple of ways - remainingWindows isn't necessary if you pass in a 'start index' into the windows array, and turning [w,x,y,z] into [x,y,z], [w,y,z] [w,x,y], ... by copying it from scratch instead of just substituting one element is pretty inefficient. [a copy would then be needed when saving bestOrdering]

> Slightly tangential: we need to figure out what to do with minimized windows.
> One possibility would be to pick slots for them and then have them zoom into
> view (a la the windowManager.js map effect) already in that slot, while the
> other windows are moving into their slots. (And then reverse the effect when
> leaving the overview.) I guess we'd still want to pick their slots based on
> their unminimized position though, so that if you then selected a minimized
> window, there'd still be a minimum of motion when leaving the overview.

Hmm, I'm not sure exactly what we do now, but wouldn't it work OK to just show them immediately in their unminimized position?  I assume meta_window_get_outer_rect returns that.

Fixed up for all other comments (and they were good ones!)

(In reply to comment #11)
> > Slightly tangential: we need to figure out what to do with minimized windows.

> Hmm, I'm not sure exactly what we do now, but wouldn't it work OK to just show
> them immediately in their unminimized position?

That's what we do now, but it's jarring to have them just blink into existence when you click "Activities" and then blink back out of existence just as the animation finishes when you leave the overview. bug 571109 was moving towards a solution for this but then the taskbar went away.

(In reply to comment #10)
> 
> function computeBestOrdering(windows, positions) {

Looks reasonable. The overall question is how many more windows can constant factor improvements like this buy us?  

6! = 720
7! = 5040
8! = 40320
9! = 362880

My guess here is that 8! is a hard limit.  

If we're optimizing here though, might as well rewrite in C.  Tentatively thinking src/shell-workspaces-native.c; opinions?

Something like:

/**
 * shell_workspaces_order_minimum_motion:
 * @length:
 * @windows: (inout) (array length=length): Array containing window geometry
 * @slots: (in) (array length=length): Array containing slots in which windows should be placed
 */
void
shell_workspaces_order_minimum_motion (int length, MetaRectangle *windows, MetaRectangle *slots);

Would need to double check binding status of inout arrays of boxed.

And should we land this JS prototype first and do optimzations here later?  Or should I try it now?

(In reply to comment #13)
> (In reply to comment #10)
> > 
> > function computeBestOrdering(windows, positions) {
> 
> Looks reasonable. The overall question is how many more windows can constant
> factor improvements like this buy us?  
> 
> 6! = 720
> 7! = 5040
> 8! = 40320
> 9! = 362880
> 
> My guess here is that 8! is a hard limit.  

let see. We can compute the full N*M set of squared distances ahead of time and it will easily fit in cache. We can write the function non-recursively since we know the stack depth ahead of time. I bet you can get it down so that the per-permutation work is something like:

 An add-and-multiply to compute the lookup index
 A lookup from the L1 cache
 An addition to compute the new score
 A well-predicted comparison
 A branch

So maybe 10 cycles. Let's say 20 to be conservative. if we're willing to take a millisecond to compute the optimum layout for a workspace, on a 1Ghz processor that would be 50000 permutations. So, you are probably about right. If we went with 10 cycles/5millseconds,2Ghz, then we could do a million permutations and handle 9 windows this way.

> If we're optimizing here though, might as well rewrite in C.  Tentatively
> thinking src/shell-workspaces-native.c; opinions?

IMO, commit a reasonably efficient JS prototype and if we like the behavior we can write it in C to go from 6 to 8 windows later. (I'd probably make the C code abstract - just take two arrays of points (here the center points of the windows and figure out the best ordering based on the two arrays.)

Attachment 143641 [details] pushed as 7703bee - [workspaces] Use a stable minimum-motion placement for windows