Эффективность против простоты
by hugeping on 2020-09-08 20: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/ [1] — принцип простоты до абсурда.
А можем пытаться выбрать что-то среднее. Но только ведь мы мечтаем об идеальном коде! А идеалы не терпят компромиссов. Так что в качестве отдушины, я пользуюсь на ноутбуке OpenBSD. А в INSTEAD я стараюсь придерживаться серединного пути. Но все-таки, все-таки все идеи приходят из мира идеального. Так что, даже в ядре Linux мы можем увидеть отголоски кода нашей мечты. :)