# Эффективность против простоты
hugeping(ping,1) — All
2020-09-08 18:53:37


Простой код — изящный и понятный код. Он работает предсказуемым образом, в нём легко выявить ошибки ещё на стадии написания. Наконец, он просто красив! Какой программист не стремится к простому коду? Когда мы представляем себе идеальный код — мы обычно имеем в виду именно простой, красивый исходный код! Но почему мы пишем нечто совсем другое?

Уравнение прямой — что может быть проще?

Ах + Ву + С = 0

Формула существует в мире идеальном. Но попробуем нарисовать отрезок прямой в грубой действительности — на растровом мониторе. Мы можем, конечно, выразить y через x и, увеличивая на 1 x, рассчитывать y. (Или x от y, для вертикальных отрезков). Потом ставить пиксель в координаты (x, y). Простой алгоритм. Только, никто так не делает. Медленно, неэффективно. Вы наверняка слышали об алгоритме Брезенхэма, который используется в таких случаях. К примеру, реализация рисования отрезка в INSTEAD (на C), выглядит так:

static __inline void line0(struct lua_pixels *hdr, int x1, int y1, int dx, int dy, int xd, unsigned char *col)
{
    int dy2 = dy * 2;
    int dyx2 = dy2 - dx * 2;
    int err = dy2 - dx;
    unsigned char *ptr = NULL;
    int w = hdr->w; int h = hdr->h;    int ly = w * 4;
    int lx = xd * 4;    while ((x1 < 0 || y1 < 0 || x1 >= w) && dx --) {
        if (err >= 0) {
            y1 ++;
            err += dyx2;
        } else {
            err += dy2;
        }
        x1 += xd;
    }
    if (dx < 0)
        return;
    ptr = (unsigned char*)(hdr + 1);
    ptr += (y1 * w + x1) << 2;    pixel(col, ptr);
    while (dx --) {
        if (err >= 0) {
            y1 ++;
            if (y1 >= h)
                break;
            ptr += ly;
            err += dyx2;
        } else {
            err += dy2;
        }
        x1 += xd;
        if (x1 >= w || x1 < 0)
            break;
        ptr += lx;
        pixel(col, ptr);
    }
    return;
}

static __inline void line1(struct lua_pixels *hdr, int x1, int y1, int dx, int dy, int xd, unsigned char *col)
{
    int dx2 = dx * 2;
    int dxy2 = dx2 - dy * 2;
    int err = dx2 - dy;
    int w = hdr->w; int h = hdr->h;
    unsigned char *ptr = NULL;
    int ly = w * 4;
    int lx = xd * 4;    while ((x1 < 0 || y1 < 0 || x1 >= w) && dy --) {
        if (err >= 0) {
                x1 += xd;
            err += dxy2;
        } else {
            err += dx2;
        }
        y1 ++;
    }
    if (dy < 0)
        return;    ptr = (unsigned char*)(hdr + 1);
    ptr += (y1 * w + x1) << 2;    pixel(col, ptr);    while (dy --) {
        if (err >= 0) {
            x1 += xd;
            if (x1 < 0 || x1 >= w)
                break;
            ptr += lx;
            err += dxy2;
        } else {
            err += dx2;
        }
        y1 ++;
        if (y1 >= h)
            break;
        ptr += ly;
        pixel(col, ptr);
    }
    return;
}

static void line(struct lua_pixels *src, 
int x1, int y1, int x2, int y2, 
int r, int g, int b, int a)
{
    int dx, dy, tmp;
    unsigned char col[4];
    if (y1 > y2) {
        tmp = y1; y1 = y2; y2 = tmp;
        tmp = x1; x1 = x2; x2 = tmp;
    }
    col[0] = r; col[1] = g; col[2] = b; col[3] = a;
    if (y1 >= src->h)
        return;
    if (y2 < 0)
        return;
    if (x1 < x2) {
        if (x2 < 0)
            return;
        if (x1 >= src->w)
            return;
    } else {
        if (x1 < 0)
            return;
        if (x2 >= src->w)
            return;
    }
    dx = x2 - x1;
    dy = y2 - y1;
    if (dx > 0) {
        if (dx > dy) {
            line0(src, x1, y1, dx, dy, 1, col);
        } else {
            line1(src, x1, y1, dx, dy, 1, col);
        }
    } else {
        dx = -dx;
        if (dx > dy) {
            line0(src, x1, y1, dx, dy, -1, col);
        } else {
            line1(src, x1, y1, dx, dy, -1, col);
        }
    }
    src->dirty = 1;
}

И это — весрия без анти-альясинга… Согласитесь, понять из алгоритма, что именно он делает, не так-то просто…

С одной стороны — простое уравнение. С другой — десятки строчек низкоуровнего кода, в которых отражена дискретная действительность наших компьютеров.

Я очень люблю OpenBSD за её простоту. Если сравнивать с современным Linux — это небо и земля! Но я понимаю, что за простоту пришлось заплатить… эффективностью. Ядро Linux очень сложное! Очень хитрые способы синхронизации (взять хотя бы rcu) разросшийся код системных вызовов… Даже если сравнивать один и тот же код разных версий — разница будет видна невооружённым глазом. Например, код из версии ядра 3.16:

void __napi_complete(struct napi_struct *n)
{
    BUG_ON(!test_bit(NAPI_STATE_SCHED, &n->state));
    BUG_ON(n->gro_list);
    list_del(&n->poll_list);
    smp_mb__before_atomic();
    clear_bit(NAPI_STATE_SCHED, &n->state);
}
void napi_complete(struct napi_struct *n)
{
    unsigned long flags;`    /*
     * don't let napi dequeue from the cpu poll list
     * just in case its running on a different cpu
     */
    if (unlikely(test_bit(NAPI_STATE_NPSVC, &n->state)))
        return;`    napi_gro_flush(n, false);
    local_irq_save(flags);
    __napi_complete(n);
    local_irq_restore(flags);
}

А вот аналогичный код, но уже из 4.18

bool napi_complete_done(struct napi_struct *n, int work_done)
{
    unsigned long flags, val, new;    /*
     * 1) Don't let napi dequeue from the cpu poll list
     *    just in case its running on a different cpu.
     * 2) If we are busy polling, do nothing here, we have
     *    the guarantee we will be called later.
     */
    if (unlikely(n->state & (NAPIF_STATE_NPSVC |
                 NAPIF_STATE_IN_BUSY_POLL)))
        return false;    if (n->gro_list) {
        unsigned long timeout = 0;        if (work_done)
            timeout = n->dev->gro_flush_timeout;        if (timeout)
            hrtimer_start(&n->timer, ns_to_ktime(timeout),
                      HRTIMER_MODE_REL_PINNED);
        else
            napi_gro_flush(n, false);
    }
    if (unlikely(!list_empty(&n->poll_list))) {
        /* If n->poll_list is not empty, we need to mask irqs */
        local_irq_save(flags);
        list_del_init(&n->poll_list);
        local_irq_restore(flags);
    }    do {
        val = READ_ONCE(n->state);        WARN_ON_ONCE(!(val & NAPIF_STATE_SCHED));        new = val & ~(NAPIF_STATE_MISSED | NAPIF_STATE_SCHED);        /* If STATE_MISSED was set, leave STATE_SCHED set,
         * because we will call napi->poll() one more time.
         * This C code was suggested by Alexander Duyck to help gcc.
         */
        new |= (val & NAPIF_STATE_MISSED) / NAPIF_STATE_MISSED *
                            NAPIF_STATE_SCHED;
    } while (cmpxchg(&n->state, val, new) != val);    if (unlikely(val & NAPIF_STATE_MISSED)) {
        __napi_schedule(n);
        return false;
    }    return true;
}
EXPORT_SYMBOL(napi_complete_done);

Кроме очевидного увеличения объёма кода тут присутствует любопытный фрагмент. Обратите внимание на конструкцию:

new |= (val & NAPIF_STATE_MISSED) / NAPIF_STATE_MISSED * NAPIF_STATE_SCHED;

Попробуйте самостоятельно понять, что она значит. Это яркий пример встречи мира идеального и мира материального. К счастью, над этой строчкой присутствует комментарий, который описывает назначение кода.

Сложность кода растёт, простота теряется… Нельзя назвать ядро Linux примером плохого кода, но и красивым этот код можно назвать лишь с натяжкой.

К сожалению, мир в котором мы живём — это мир компромиссов.

Мы можем следовать одному из принципов:

- Linux — стихийная хакерская разработка;
- OpenBSD — принцип простоты в абсолюте;
- Проект https://suckless.org/ — принцип простоты до абсурда.

А можем пытаться выбрать что-то среднее. Но только ведь мы мечтаем об идеальном коде! А идеалы не терпят компромиссов. Так что в качестве отдушины, я пользуюсь на ноутбуке OpenBSD. А в INSTEAD я стараюсь придерживаться серединного пути. Но все-таки, все-таки все идеи приходят из мира идеального. Так что, даже в ядре Linux мы можем увидеть отголоски кода нашей мечты. :)