Created attachment 147988 [details]
Screenshoot

It's hard to me to figure out what the idea of the patch is from reading the patch. Can you explain what you are trying to solve and the algorithm in more detail here?

Created attachment 149919 [details] [review]
Improve the window sizing/layout in the overlay.

(Updated to latest master 20294f2c9204087880e8d379e374789a31793f6a by me)

It looks like the algorithm is:

* Divide the windows into groups where the windows in the group don't intersect
* We use a number of slots which is equal to the number of groups
* For each slot, divide the windows inside that slot

Under which situations this is better/worse than the old way would need some more thought; on my netbook it's exactly the same since all windows on it are maximized (and thus overlap).  I'll need to try it on my home machine.

Review of attachment 149919 [details] [review]:

I'd still like to see a high level description of what problems you saw with the old system, and how this one is better.

Partial review follows:

::: js/ui/workspaces.js
@@ +892,3 @@
+                let ret = (x >= rect.x) && (x <= rect.x + rect.width);
+            function inner(rect, x, y) {
+        function intersect(w1, w2) {

This is inefficient; you're losing the short-circuiting effect that || provides.  You really want:

 return inner() || inner () || inner ()
  || inner ().

But:

@@ +898,3 @@
+                return ret;
+                ret = ret && (y >= rect.y) && (y <= rect.y + rect.height);
+            function inner(rect, x, y) {

There's a more efficient way to determine if two rectangles intersect;

return ! (r1.x + r1.width < r2.x || r1.y + r1.height < r2.y || r1.x > r2.x + r2.width || r1.y > r2.y + r2.height);

And actually, looking around a bit, there's a meta_rectangle_overlap method, so:

function intersect(w1, w2) {
    let r1 = new Meta.Rectangle();
    w1.get_outer_rect(r1);
    let r2 = new Meta.Rectangle();
    w2.get_outer_rect(r2);
    return r1.overlap(r2);
}

(You can find this as windows_overlap in mutter/src/core/windows.c)

@@ +915,3 @@
+            group.push(i);
+                continue;
+            if (used[i] !== undefined)

Likewise here:

 if (intersect) {
   b = intersect(...);
   if (b)
     break;
 }

I'd prefer "let intersecting = false;" rather than just "b" too.

just a rough overview of why the current algorithm is not good: it allocates the same scaling factor to all windows on a workspace

using the same factor makes small windows really small; all distinguishing features of a window are blurred together into a white/grey-ish blob, and it makes them a hard target to hit - especially with crappy pointer devices. this also makes it look like *a lot* of space gets wasted; compare with OSX's exposé:

  http://www.flickr.com/photos/drkpnk/476322516/

obviously, these considerations do not apply to exactly one scenario: if you use only maximized windows; with only maximized windows the effect of the current algorithm are masked because the windows have all exactly the same size, and the scaling factor requires a bigger number of windows on the same workspace to make them small blobs.

I'll try attachment 149919 [details] [review], update it and try to address the issues Colin's review outlined.

compare and contrast with the result of the current algorithm on my laptop; the primary panel is 1280x800, and the windows are various non homogeneous sizes:

  http://folks.o-hand.com/ebassi/overview.png

(In reply to comment #6)
> just a rough overview of why the current algorithm is not good: it allocates
> the same scaling factor to all windows on a workspace

If I recall correctly the rationale was that a window's size in relation to others helps identifying windows (think of two editor windows, one maximized).

(In reply to comment #7)
> compare and contrast with the result of the current algorithm on my laptop; the
> primary panel is 1280x800, and the windows are various non homogeneous sizes:
> 
>   http://folks.o-hand.com/ebassi/overview.png

The problem here is not so much the window positioning, but that we handle dual-monitor setups badly. Workspaces in the overview are based on the _screen_ size, which are scaled down to fit the monitor, wasting a huge amount of space above and below the workspace.

See bug 609258.

(In reply to comment #9)
> (In reply to comment #7)
> > compare and contrast with the result of the current algorithm on my laptop; the
> > primary panel is 1280x800, and the windows are various non homogeneous sizes:
> > 
> >   http://folks.o-hand.com/ebassi/overview.png
> 
> The problem here is not so much the window positioning, but that we handle
> dual-monitor setups badly. Workspaces in the overview are based on the _screen_
> size, which are scaled down to fit the monitor, wasting a huge amount of space
> above and below the workspace.

that might be true, but I see the same waste - or, better, far too much wasted space - when I run with a single panel.

(In reply to comment #8)
> (In reply to comment #6)
> > just a rough overview of why the current algorithm is not good: it allocates
> > the same scaling factor to all windows on a workspace
> 
> If I recall correctly the rationale was that a window's size in relation to
> others helps identifying windows (think of two editor windows, one maximized).

it's not just shape: it's also content. a small window to start with will be easier to recognize against a bigger one. on the other hand, I agree: trying to maintain some regular ratio aids visual recognition.

a combined approach of bucketing the sizes - i.e. partitioning the set of sizes to various boxes with the same regular ratio - seems like the best compromise.

(In reply to comment #8)
> (In reply to comment #6)
> > just a rough overview of why the current algorithm is not good: it allocates
> > the same scaling factor to all windows on a workspace
> 
> If I recall correctly the rationale was that a window's size in relation to
> others helps identifying windows (think of two editor windows, one maximized).

Wait a moment here, we don't use a constant scale between windows - each window is scaled up independently. Try creating a really small window and go to the overview. The only constraint is supposed to be that we never scale windows *up* that that seems broken in the latest version and we scale windows up by a small amount.

Thanks for the bug report. This particular bug has already been reported into our bug tracking system, but please feel free to report any further bugs you find.

*** This bug has been marked as a duplicate of bug 582650 ***