From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:46298) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Vilwq-0005wc-R9 for qemu-devel@nongnu.org; Tue, 19 Nov 2013 09:06:42 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Vilwl-0001EJ-6J for qemu-devel@nongnu.org; Tue, 19 Nov 2013 09:06:36 -0500 Received: from mx.ipv6.kamp.de ([2a02:248:0:51::16]:47425 helo=mx01.kamp.de) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Vilwk-0001E4-J9 for qemu-devel@nongnu.org; Tue, 19 Nov 2013 09:06:31 -0500 Message-ID: <528B706D.3080705@kamp.de> Date: Tue, 19 Nov 2013 15:06:37 +0100 From: Peter Lieven MIME-Version: 1.0 References: <1384762641-18297-1-git-send-email-pl@kamp.de> <1384762641-18297-3-git-send-email-pl@kamp.de> <528B6C40.2030401@kamp.de> In-Reply-To: <528B6C40.2030401@kamp.de> Content-Type: multipart/alternative; boundary="------------050804030803060608040809" Subject: Re: [Qemu-devel] [PATCH 2/3] ui/vnc: optimize dirty bitmap tracking List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Anthony Liguori Cc: corentincj@iksaif.net, qemu-devel@nongnu.org This is a multi-part message in MIME format. --------------050804030803060608040809 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit On 19.11.2013 14:48, Peter Lieven wrote: > On 18.11.2013 17:27, Anthony Liguori wrote: >> >> >> On Nov 18, 2013 12:20 AM, "Peter Lieven" > wrote: >> > >> > vnc_update_client currently scans the dirty bitmap of each client >> > bitwise which is a very costly operation if only few bits are dirty. >> > vnc_refresh_server_surface does almost the same. >> > this patch optimizes both by utilizing the heavily optimized >> > function find_next_bit to find the offset of the next dirty >> > bit in the dirty bitmaps. >> > >> > Signed-off-by: Peter Lieven > >> >> Can you include performance data? >> > > I made some aritificial analysis of vnc_update_client with the attached test code. > > $ gcc -O2 -o vnc_perf vnc_perf.c > $ ./vnc_perf > All bits clean - vnc_update_client_new: 0.07 secs > vnc_update_client_old: 10.82 secs > > All bits dirty - vnc_update_client_new: 9.81 secs > vnc_update_client_old: 20.00 secs > > Few bits dirty - vnc_update_client_new: 0.08 secs > vnc_update_client_old: 10.62 secs > > find_and_clear_dirty_height() is still very slow, but I will look at this separately. quite easy, but great effect: replacing: for (tmp_x = last_x; tmp_x < x; tmp_x++) { clear_bit(tmp_x, dirty[y + h]); } with: bitmap_clear(dirty[y + h], last_x, x - last_x); in find_and_clear_dirty_height(), yields the following performance ;-) All bits clean - vnc_update_client_new: 0.07 secs vnc_update_client_old: 10.65 secs All bits dirty - vnc_update_client_new: 0.69 secs vnc_update_client_old: 19.86 secs Few bits dirty - vnc_update_client_new: 0.07 secs vnc_update_client_old: 10.69 secs > Peter > > --- > > #define ITERATIONS 16*1024 > > #define VNC_MAX_WIDTH 2560 > #define VNC_MAX_HEIGHT 2048 > > #define VNC_DIRTY_PIXELS_PER_BIT 16 > > /* VNC_DIRTY_BITS is the number of bits in the dirty bitmap. */ > #define VNC_DIRTY_BITS (VNC_MAX_WIDTH / VNC_DIRTY_PIXELS_PER_BIT) > > /* VNC_DIRTY_BITS_PER_LINE might be greater than VNC_DIRTY_BITS due to alignment */ > #define VNC_DIRTY_BITS_PER_LINE(x) (sizeof(x) / VNC_MAX_HEIGHT * BITS_PER_BYTE) > > #define BITS_PER_BYTE 8 > #define BITS_PER_LONG (sizeof (unsigned long) * BITS_PER_BYTE) > > #define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) > > #define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d)) > > #define BIT(nr) (1UL << (nr)) > #define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG)) > #define BIT_WORD(nr) ((nr) / BITS_PER_LONG) > #define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long)) > > #define DECLARE_BITMAP(name,bits) \ > unsigned long name[BITS_TO_LONGS(bits)] > > #define ctzl ctz64 > > #include > #include > #include > #include "time.h" > > static inline int ctz64(uint64_t val) > { > return val ? __builtin_ctzll(val) : 64; > } > > DECLARE_BITMAP(dirty[VNC_MAX_HEIGHT], VNC_DIRTY_BITS); > > unsigned long find_next_bit(const unsigned long *addr, unsigned long size, > unsigned long offset) > { > const unsigned long *p = addr + BITOP_WORD(offset); > unsigned long result = offset & ~(BITS_PER_LONG-1); > unsigned long tmp; > > if (offset >= size) { > return size; > } > size -= result; > offset %= BITS_PER_LONG; > if (offset) { > tmp = *(p++); > tmp &= (~0UL << offset); > if (size < BITS_PER_LONG) { > goto found_first; > } > if (tmp) { > goto found_middle; > } > size -= BITS_PER_LONG; > result += BITS_PER_LONG; > } > while (size >= 4*BITS_PER_LONG) { > unsigned long d1, d2, d3; > tmp = *p; > d1 = *(p+1); > d2 = *(p+2); > d3 = *(p+3); > if (tmp) { > goto found_middle; > } > if (d1 | d2 | d3) { > break; > } > p += 4; > result += 4*BITS_PER_LONG; > size -= 4*BITS_PER_LONG; > } > while (size >= BITS_PER_LONG) { > if ((tmp = *(p++))) { > goto found_middle; > } > result += BITS_PER_LONG; > size -= BITS_PER_LONG; > } > if (!size) { > return result; > } > tmp = *p; > > found_first: > tmp &= (~0UL >> (BITS_PER_LONG - size)); > if (tmp == 0UL) { /* Are any bits set? */ > return result + size; /* Nope. */ > } > found_middle: > return result + ctzl(tmp); > } > > static inline int test_bit(int nr, const unsigned long *addr) > { > return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1))); > } > > static inline void clear_bit(int nr, unsigned long *addr) > { > unsigned long mask = BIT_MASK(nr); > unsigned long *p = addr + BIT_WORD(nr); > > *p &= ~mask; > } > > static inline void set_bit(int nr, unsigned long *addr) > { > unsigned long mask = BIT_MASK(nr); > unsigned long *p = addr + BIT_WORD(nr); > > *p |= mask; > } > > static inline int test_and_clear_bit(int nr, unsigned long *addr) > { > unsigned long mask = BIT_MASK(nr); > unsigned long *p = addr + BIT_WORD(nr); > unsigned long old = *p; > > *p = old & ~mask; > return (old & mask) != 0; > } > > static int find_and_clear_dirty_height(int y, int last_x, int x, int height) > { > int h; > > for (h = 1; h < (height - y); h++) { > int tmp_x; > if (!test_bit(last_x, dirty[y + h])) { > break; > } > for (tmp_x = last_x; tmp_x < x; tmp_x++) { > clear_bit(tmp_x, dirty[y + h]); > } > } > > return h; > } > > #define VNC_CLIENT_UPDATE_RECT() \ > if (last_x != -1) {\ > int h = find_and_clear_dirty_height(y, last_x, x, height);\ > } > > void vnc_update_client_new() { > int width = VNC_MAX_WIDTH; > int height = VNC_MAX_HEIGHT; > int y = 0; > for (;;) { > int x; > int last_x = -1; > unsigned long offset = find_next_bit((unsigned long *) &dirty, > height * VNC_DIRTY_BITS_PER_LINE(dirty), > y * VNC_DIRTY_BITS_PER_LINE(dirty)); > if (offset == height * VNC_DIRTY_BITS_PER_LINE(dirty)) { > /* no more dirty bits */ > break; > } > y = offset / VNC_DIRTY_BITS_PER_LINE(dirty); > > for (x = offset % VNC_DIRTY_BITS_PER_LINE(dirty); > x < width / VNC_DIRTY_PIXELS_PER_BIT; x++) { > if (test_and_clear_bit(x, dirty[y])) { > if (last_x == -1) { > last_x = x; > } > } else { > VNC_CLIENT_UPDATE_RECT(); > last_x = -1; > } > } > VNC_CLIENT_UPDATE_RECT(); > y++; > }} > > void vnc_update_client_old() { > int width = VNC_MAX_WIDTH; > int height = VNC_MAX_HEIGHT; > int y; > for (y = 0; y < height; y++) { > int x; > int last_x = -1; > for (x = 0; x < width / 16; x++) { > if (test_and_clear_bit(x, dirty[y])) { > if (last_x == -1) { > last_x = x; > } > } else { > VNC_CLIENT_UPDATE_RECT(); > last_x = -1; > } > } > VNC_CLIENT_UPDATE_RECT(); > } > } > > void main() { > int i; > clock_t start, end; > start = clock(); > for (i = 0; i < ITERATIONS; i++) { > memset(dirty, 0x00, sizeof(dirty)); > vnc_update_client_new(); > } > end = clock(); > printf("All bits clean - vnc_update_client_new: %.2f secs\n", (double) (end-start)/CLOCKS_PER_SEC); > start = clock(); > for (i = 0; i < ITERATIONS; i++) { > memset(dirty, 0x00, sizeof(dirty)); > vnc_update_client_old(); > } > end = clock(); > printf(" vnc_update_client_old: %.2f secs\n\n", (double) (end-start)/CLOCKS_PER_SEC); > start = clock(); > for (i = 0; i < ITERATIONS; i++) { > memset(dirty, 0xff, sizeof(dirty)); > vnc_update_client_new(); > } > end = clock(); > printf("All bits dirty - vnc_update_client_new: %.2f secs\n", (double) (end-start)/CLOCKS_PER_SEC); > start = clock(); > for (i = 0; i < ITERATIONS; i++) { > memset(dirty, 0xff, sizeof(dirty)); > vnc_update_client_old(); > } > end = clock(); > printf(" vnc_update_client_old: %.2f secs\n\n", (double) (end-start)/CLOCKS_PER_SEC); > start = clock(); > for (i = 0; i < ITERATIONS; i++) { > int y; > memset(dirty, 0x00, sizeof(dirty)); > for (y = VNC_MAX_HEIGHT/2-8; y < VNC_MAX_HEIGHT/2+8; y++) { > set_bit(VNC_DIRTY_BITS/2,dirty[y]); > } > vnc_update_client_new(); > } > end = clock(); > printf("Few bits dirty - vnc_update_client_new: %.2f secs\n", (double) (end-start)/CLOCKS_PER_SEC); > start = clock(); > for (i = 0; i < ITERATIONS; i++) { > int y; > memset(dirty, 0x00, sizeof(dirty)); > for (y = VNC_MAX_HEIGHT/2-8; y < VNC_MAX_HEIGHT/2+8; y++) { > set_bit(VNC_DIRTY_BITS/2,dirty[y]); > } > vnc_update_client_old(); > } > end = clock(); > printf(" vnc_update_client_old: %.2f secs\n\n", (double) (end-start)/CLOCKS_PER_SEC); > return; > } > -- Mit freundlichen Grüßen Peter Lieven ........................................................... KAMP Netzwerkdienste GmbH Vestische Str. 89-91 | 46117 Oberhausen Tel: +49 (0) 208.89 402-50 | Fax: +49 (0) 208.89 402-40 pl@kamp.de | http://www.kamp.de Geschäftsführer: Heiner Lante | Michael Lante Amtsgericht Duisburg | HRB Nr. 12154 USt-Id-Nr.: DE 120607556 ........................................................... --------------050804030803060608040809 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit
On 19.11.2013 14:48, Peter Lieven wrote:
On 18.11.2013 17:27, Anthony Liguori wrote:


On Nov 18, 2013 12:20 AM, "Peter Lieven" <pl@kamp.de> wrote:
>
> vnc_update_client currently scans the dirty bitmap of each client
> bitwise which is a very costly operation if only few bits are dirty.
> vnc_refresh_server_surface does almost the same.
> this patch optimizes both by utilizing the heavily optimized
> function find_next_bit to find the offset of the next dirty
> bit in the dirty bitmaps.
>
> Signed-off-by: Peter Lieven <pl@kamp.de>

Can you include performance data?


I made some aritificial analysis of vnc_update_client with the attached test code.

$ gcc -O2  -o vnc_perf vnc_perf.c
$ ./vnc_perf
All bits clean - vnc_update_client_new: 0.07 secs
                 vnc_update_client_old: 10.82 secs

All bits dirty - vnc_update_client_new: 9.81 secs
                 vnc_update_client_old: 20.00 secs

Few bits dirty - vnc_update_client_new: 0.08 secs
                 vnc_update_client_old: 10.62 secs

find_and_clear_dirty_height() is still very slow, but I will look at this separately.
quite easy, but great effect:

replacing:

         for (tmp_x = last_x; tmp_x < x; tmp_x++) {
             clear_bit(tmp_x, dirty[y + h]);
         }

with:

        bitmap_clear(dirty[y + h], last_x, x - last_x);

in find_and_clear_dirty_height(), yields the following performance ;-)

All bits clean - vnc_update_client_new: 0.07 secs
                 vnc_update_client_old: 10.65 secs

All bits dirty - vnc_update_client_new: 0.69 secs
                 vnc_update_client_old: 19.86 secs

Few bits dirty - vnc_update_client_new: 0.07 secs
                 vnc_update_client_old: 10.69 secs


Peter

---

#define ITERATIONS 16*1024

#define VNC_MAX_WIDTH 2560
#define VNC_MAX_HEIGHT 2048

#define VNC_DIRTY_PIXELS_PER_BIT 16

/* VNC_DIRTY_BITS is the number of bits in the dirty bitmap. */
#define VNC_DIRTY_BITS (VNC_MAX_WIDTH / VNC_DIRTY_PIXELS_PER_BIT)

/* VNC_DIRTY_BITS_PER_LINE might be greater than VNC_DIRTY_BITS due to alignment */
#define VNC_DIRTY_BITS_PER_LINE(x) (sizeof(x) / VNC_MAX_HEIGHT * BITS_PER_BYTE)

#define BITS_PER_BYTE           8
#define BITS_PER_LONG           (sizeof (unsigned long) * BITS_PER_BYTE)

#define BITOP_WORD(nr)        ((nr) / BITS_PER_LONG)

#define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d))

#define BIT(nr)            (1UL << (nr))
#define BIT_MASK(nr)        (1UL << ((nr) % BITS_PER_LONG))
#define BIT_WORD(nr)        ((nr) / BITS_PER_LONG)
#define BITS_TO_LONGS(nr)    DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))

#define DECLARE_BITMAP(name,bits)                  \
    unsigned long name[BITS_TO_LONGS(bits)]

#define ctzl ctz64

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include "time.h"

static inline int ctz64(uint64_t val)
{
    return val ? __builtin_ctzll(val) : 64;
}

DECLARE_BITMAP(dirty[VNC_MAX_HEIGHT], VNC_DIRTY_BITS);

unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
                unsigned long offset)
{
    const unsigned long *p = addr + BITOP_WORD(offset);
    unsigned long result = offset & ~(BITS_PER_LONG-1);
    unsigned long tmp;

    if (offset >= size) {
        return size;
    }
    size -= result;
    offset %= BITS_PER_LONG;
    if (offset) {
        tmp = *(p++);
        tmp &= (~0UL << offset);
        if (size < BITS_PER_LONG) {
            goto found_first;
        }
        if (tmp) {
            goto found_middle;
        }
        size -= BITS_PER_LONG;
        result += BITS_PER_LONG;
    }
    while (size >= 4*BITS_PER_LONG) {
        unsigned long d1, d2, d3;
        tmp = *p;
        d1 = *(p+1);
        d2 = *(p+2);
        d3 = *(p+3);
        if (tmp) {
            goto found_middle;
        }
        if (d1 | d2 | d3) {
            break;
        }
        p += 4;
        result += 4*BITS_PER_LONG;
        size -= 4*BITS_PER_LONG;
    }
    while (size >= BITS_PER_LONG) {
        if ((tmp = *(p++))) {
            goto found_middle;
        }
        result += BITS_PER_LONG;
        size -= BITS_PER_LONG;
    }
    if (!size) {
        return result;
    }
    tmp = *p;

found_first:
    tmp &= (~0UL >> (BITS_PER_LONG - size));
    if (tmp == 0UL) {        /* Are any bits set? */
        return result + size;    /* Nope. */
    }
found_middle:
    return result + ctzl(tmp);
}

static inline int test_bit(int nr, const unsigned long *addr)
{
    return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1)));
}

static inline void clear_bit(int nr, unsigned long *addr)
{
    unsigned long mask = BIT_MASK(nr);
        unsigned long *p = addr + BIT_WORD(nr);

    *p &= ~mask;
}

static inline void set_bit(int nr, unsigned long *addr)
{
    unsigned long mask = BIT_MASK(nr);
        unsigned long *p = addr + BIT_WORD(nr);

    *p  |= mask;
}

static inline int test_and_clear_bit(int nr, unsigned long *addr)
{
    unsigned long mask = BIT_MASK(nr);
        unsigned long *p = addr + BIT_WORD(nr);
    unsigned long old = *p;

    *p = old & ~mask;
    return (old & mask) != 0;
}

static int find_and_clear_dirty_height(int y, int last_x, int x, int height)
{
    int h;

    for (h = 1; h < (height - y); h++) {
        int tmp_x;
        if (!test_bit(last_x, dirty[y + h])) {
            break;
        }
        for (tmp_x = last_x; tmp_x < x; tmp_x++) {
            clear_bit(tmp_x, dirty[y + h]);
        }
    }

    return h;
}

#define VNC_CLIENT_UPDATE_RECT() \
    if (last_x != -1) {\
        int h = find_and_clear_dirty_height(y, last_x, x, height);\
    }

void vnc_update_client_new() {
        int width = VNC_MAX_WIDTH;
        int height = VNC_MAX_HEIGHT;
        int y = 0;
        for (;;) {
            int x;
            int last_x = -1;
            unsigned long offset = find_next_bit((unsigned long *) &dirty,
                                                 height * VNC_DIRTY_BITS_PER_LINE(dirty),
                                                 y * VNC_DIRTY_BITS_PER_LINE(dirty));
            if (offset == height * VNC_DIRTY_BITS_PER_LINE(dirty)) {
                /* no more dirty bits */
                break;
            }
            y = offset / VNC_DIRTY_BITS_PER_LINE(dirty);

            for (x = offset % VNC_DIRTY_BITS_PER_LINE(dirty);
                 x < width / VNC_DIRTY_PIXELS_PER_BIT; x++) {
                if (test_and_clear_bit(x, dirty[y])) {
                    if (last_x == -1) {
                        last_x = x;
                    }
                } else {
                    VNC_CLIENT_UPDATE_RECT();
                    last_x = -1;
                }
            }
            VNC_CLIENT_UPDATE_RECT();
            y++;
        }}

void vnc_update_client_old() {
        int width = VNC_MAX_WIDTH;
        int height = VNC_MAX_HEIGHT;
        int y;
        for (y = 0; y < height; y++) {
            int x;
            int last_x = -1;
            for (x = 0; x < width / 16; x++) {
                if (test_and_clear_bit(x, dirty[y])) {
                    if (last_x == -1) {
                        last_x = x;
                    }
                } else {
                    VNC_CLIENT_UPDATE_RECT();
                    last_x = -1;
                }
            }
            VNC_CLIENT_UPDATE_RECT();
        }
}

void main() {
    int i;
    clock_t start, end;
    start = clock();
    for (i = 0; i < ITERATIONS; i++) {
         memset(dirty, 0x00, sizeof(dirty));
         vnc_update_client_new();
    }
    end = clock();
    printf("All bits clean - vnc_update_client_new: %.2f secs\n", (double) (end-start)/CLOCKS_PER_SEC);
    start = clock();
    for (i = 0; i < ITERATIONS; i++) {
         memset(dirty, 0x00, sizeof(dirty));
         vnc_update_client_old();
    }
    end = clock();
    printf("                 vnc_update_client_old: %.2f secs\n\n", (double) (end-start)/CLOCKS_PER_SEC);
    start = clock();
    for (i = 0; i < ITERATIONS; i++) {
         memset(dirty, 0xff, sizeof(dirty));
         vnc_update_client_new();
    }
    end = clock();
    printf("All bits dirty - vnc_update_client_new: %.2f secs\n", (double) (end-start)/CLOCKS_PER_SEC);
    start = clock();
    for (i = 0; i < ITERATIONS; i++) {
         memset(dirty, 0xff, sizeof(dirty));
         vnc_update_client_old();
    }
    end = clock();
    printf("                 vnc_update_client_old: %.2f secs\n\n", (double) (end-start)/CLOCKS_PER_SEC);   
    start = clock();
    for (i = 0; i < ITERATIONS; i++) {
         int y;
         memset(dirty, 0x00, sizeof(dirty));
         for (y = VNC_MAX_HEIGHT/2-8; y < VNC_MAX_HEIGHT/2+8; y++) {
             set_bit(VNC_DIRTY_BITS/2,dirty[y]);
         }
         vnc_update_client_new();
    }
    end = clock();
    printf("Few bits dirty - vnc_update_client_new: %.2f secs\n", (double) (end-start)/CLOCKS_PER_SEC);
    start = clock();
    for (i = 0; i < ITERATIONS; i++) {
         int y;
         memset(dirty, 0x00, sizeof(dirty));
         for (y = VNC_MAX_HEIGHT/2-8; y < VNC_MAX_HEIGHT/2+8; y++) {
             set_bit(VNC_DIRTY_BITS/2,dirty[y]);
         }
         vnc_update_client_old();
    }
    end = clock();
    printf("                 vnc_update_client_old: %.2f secs\n\n", (double) (end-start)/CLOCKS_PER_SEC);   
    return;
}



-- 

Mit freundlichen Grüßen

Peter Lieven

...........................................................

  KAMP Netzwerkdienste GmbH
  Vestische Str. 89-91 | 46117 Oberhausen
  Tel: +49 (0) 208.89 402-50 | Fax: +49 (0) 208.89 402-40
  pl@kamp.de | http://www.kamp.de

  Geschäftsführer: Heiner Lante | Michael Lante
  Amtsgericht Duisburg | HRB Nr. 12154
  USt-Id-Nr.: DE 120607556

...........................................................
--------------050804030803060608040809--