The diff below adds a little improvement to the wsmouse_matching
function, which is the core of the MT tracking mechanism in wsmouse.
Sadly, that mechanism isn't in use up to now, but this also means
that OKs are riskless ;-)
With small matrices - roughly, of orders up to 300 or 400 - and most
kinds of input, the current version is faster than the alternatives that
I tested some time ago. The tests included two clean and compact O(n^3)
implementations of the "Hungarian Method" as well as the Linux
equivalent of the matching function (find_reduced_matrix in input_mt.c).
The input types were random data in various ranges, "Machol-Wien" data,
and geometric data (the type that is relevant for wsmouse).
It might not matter in wsmouse, but the current version doesn't perform
well if the range and variation of the matrix values is very small, and
matrices filled with equal values belong to the worst-case inputs. To a
large extent, this is due to a flaw of the implementation; it may
trigger superfluous searches. The change below removes this defect.
OK?
Index: dev/wscons/wsmouse.c
===================================================================
RCS file: /cvs/src/sys/dev/wscons/wsmouse.c,v
retrieving revision 1.30
diff -u -p -r1.30 wsmouse.c
--- dev/wscons/wsmouse.c 6 Jun 2016 22:32:47 -0000 1.30
+++ dev/wscons/wsmouse.c 4 Jul 2016 23:15:58 -0000
@@ -1125,11 +1125,13 @@ wsmouse_matching(int *matrix, int m, int
for (; p < alt; *p++ = 0) {}
for (col = 0; col < n; col++) {
delta = INT_MAX;
- for (i = 0, p = matrix + col; i < m; i++, p += n)
- if ((d = *p - red[i]) <= delta) {
+ for (i = 0, p = matrix + col; i < m; i++, p += n) {
+ d = *p - red[i];
+ if (d < delta || (d == delta && r2c[i] < 0)) {
delta = d;
row = i;
}
+ }
cd[col] = delta;
if (r2c[row] < 0) {
r2c[row] = col;
@@ -1151,7 +1153,8 @@ wsmouse_matching(int *matrix, int m, int
mc[i] = j;
}
d -= red[i];
- if (d <= delta) {
+ if (d < delta || (d == delta
+ && r2c[i] < 0)) {
delta = d;
row = i;
}
