Как стать автором
Поиск
Написать публикацию
Обновить

Комментарии 41

Увидел статью, обрадовался, поставил плюс не читая. Как оказалось, зря. Вы совсем не поняли смысл цикла. Он же не о замене for (i++) на for (i--), он вообще не про реализацию был, а про принципы. У вас же тут ничего о графике, одни ключи компилятора и шаблоны. Надо было как-то иначе оформить, а не как часть курса.
Всего голосов 13: ↑7 и ↓6+1
Подождите, эта работа ортогональна общему курсу статей, но. Но для того, чтобы нам было удобно писать высокоуровневый код, нужна удобная геометрическая библиотека. gbg провёл много времени над тем, чтобы геометрический код было приятно читать.

Вы ещё не видели новый растеризатор, сейчас треугольники честно рисуются проходом по всем пикселям описывающего прямоугольника! Да, это не статья про шейдеры, но так она и порядковый номер носит 3.1. Зато в пятой у нас будет простор и раздолье. Код готов, уже можете смотреть на гитхабе.
Всего голосов 8: ↑7 и ↓1+6
Очень прошу, продолжайте оба ) Такого вот материала для понимания очень не хватает! ))
Всего голосов 5: ↑4 и ↓1+3
Ваш трюк с циклом for мне кажется неуместным. Он хорош, когда действительно важно бежать с конца в начало, но, поскольку в ваших функциях вам все равно, то лучше использовать классический
for (size_t i=0; i<Dim; ++i)
Экономить 3 символа это, конечно, хорошо, но в отличие от классического варианта этот при прочтении прямо таки просит взять в руки бумажку и проверить, что тут нигде не налажали. Кроме того, отказ от него позволил бы вам сэкономить целый абзац в статье, раз уж вам это так нравиться.

Кроме того, вносить действие в шапку цикла считается признаком плохого стиля, а когда тело цикла пустое, рекомендуется вместо незаметной ; на той же строке, что и шапка, писать так:
for (size_t i=len; i--; ret[i]=v[i]) {}
или так:
for (size_t i=len; i--; ret[i]=v[i])
    ;

Все-таки это материал для новичков, поэтому надо стремиться показывать хороший код.

Всего голосов 10: ↑10 и ↓0+10
Появление этого цикла тесно связано с использованием size_t для индексации массивов.

В статье показана частая ошибка, когда для обхода массива в сторону уменьшения индекса забывают о том, что в беззнаковом случае i>=0 — всегда истина.

После этого, дается пример верного цикла, который правильно все обходит и корректно завершается. Указано, почему это происходит.

Для закрепления и запоминания, этот пример используется повсеместно. Как дополнительная демонстрация того, как верно использовать size_t даже при обходе «задом наперед».

Теперь о целесообразности такого обхода. Если не рассматривать случаи, когда алгоритм прямо требует движения «вниз», остается еще совет #61 Алена Голуба, автора книги «Веревка достаточной длины, чтобы выстрелить себе в ногу»:
Циклы являются одним из тех мест, где малое повышение эффективности значительно улучшает выполнение программы, потому что их код выполняется многократно. Так как сравнение с нулем обычно более эффективно, чем сравнение с определенным числом, то цикл с уменьшающимся счетчиком, как правило, выполняется быстрее.

Строго говоря, мы не можем полагаться на то, в какие инструкции превратит компилятор нашу программу. Более того, мы желаем, чтобы в нашей программе цикла и вовсе не было — требуем от компилятора развернуть и векторизовать эти инструкции.

Однако стоит также вспомнить, что в x86 действительно есть специальная инструкция loop, которая делает как раз то, что нужно:
  • Декремент CX,
  • затем проверка на равенство его 0
  • и если CX не 0, переход на метку


Но мы можем заставить компилятор задействовать именно ее, поэтому данный аргумент — слабый.

Итого, мы показываем «а еще с for можно поступить вот так, и это корректно». Прочитавшие могут пополнить свою копилку интересностей.

Относительно оформления — я с вами полностью согласен. Мой код этого метода в отдельной ветке на guthub оформлен так:
/////////////////////////////сумма векторов
template<size_t Dim,typename Number>vec<Dim,Number > operator+(vec<Dim,Number > lhs, const vec<Dim,Number >& rhs)
{
   for(size_t i=Dim;i--;)
   {
      lhs[i]+=rhs[i];
   }
   return(lhs);
}

Как видите, лично я против переноса тела цикла в заголовок. И я холодно отношусь к стилю расстановки {}, который применяют K&R и haqreu. Но тон проекта (tinyrenderer, где «tiny» значит, чтобы исходники были покороче) задан ранее и я ему следую.
Всего голосов 5: ↑3 и ↓2+1
ПОПРАВКА:
Но мы можем заставить компилятор задействовать именно ее, поэтому данный аргумент — слабый.


Но мы НЕ можем заставить компилятор задействовать именно ее, поэтому данный аргумент — слабый.
Всего голосов 1: ↑0 и ↓1-1
Со мной связался некто kyhtep и задал следующий вопрос:
Здравствуйте.

К сожалению, я не могу писать в комментарии к статьям.

Если вам не сложно, ответье пожалуйста на вопрос к статье
Краткий курс компьютерной графики 3.1

Вы используете обратный цикл, далее в комментарии вы мотивириуете это тем, что проверка на 0 быстрее плюс есть специальная инструкция.

Но разве при обратном проходе у вас не будут кэш мисы?

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


Еще раз кратко: Цикл показан исключительно для демонстрации и закрепления практики применения size_t для индексации массива в случае, когда нужен именно обратный обход.
Итого:
  • показана хорошая практика применения size_t,
  • показано, какие проблемы с такой практикой можно поймать,
  • показано, как этого не допустить,
  • материал закрепляется путем многократного применения на практике.

Аргумент про совет #61 Голуба даже отсутствует в статье, потому как делать предположения о том, во что компилятор странслирует программу довольно опасно — С++ — штука кроссплатформенная, и трюк, который хорошо работает на одной архитектуре может развалится (или сильно деградировать) на другой.

Конкретно в нашем случае (с -O3 -avx), компилятор и вовсе выбросит эти циклы и заменит их векторными инструкциями. Ассемблер можно посмотреть здесь, тесты по скорости — здесь.

Данный код написан в очень наивной манере. По вопросам производительности материала еще нет, нужно посмотреть стандарты, провести тесты, составить мнение.

Вопрос деградации работы с кэшем при обратном проходе большого массива пока что — открыт и занесен в TODO. Пока что я предполагаю, что данный совет Голуба довольно рискован, но ничего утверждать не могу.

Резюме — мы ходим по массивам задом наперед только лишь для закрепления самого способа хождения. Вопрос о том, что такой проход будет быстрее (как утверждает Голуб) — открыт и стоит в TODO.
Всего голосов 4: ↑2 и ↓20
100 и 1 способ выстрелить себе в ногу. Вы пишете на С++, почему бы не использовать стандартные алгоритмы?

std::transform(lhs.begin(), lhs.end(), rhs.begin(), lhs.begin(), std::minus<int>());
Всего голосов 2: ↑1 и ↓10
К сожалению, ваше предложение серьезно нарушает идею KISS, которой мы стараемся придерживаться.

Так как мы работаем в рамках C++98, мы к сожалению не располагаем std::array. Это значит, что нам придется адаптировать свой вектор для работы с STL (писать begin(), end(), возвращающие итератор (который тоже придется писать)). Польза от такого нововведения сомнительна.

Второй вариант — хранить все данные внутри std::vector. Но вектор предназначен для хранения динамических массивов — он и память для своего содержимого берет из кучи (хотя на это еще можно повлиять, дав ему другой аллокатор), и хранит внутри себя количество элементов (а в нашем случае, это константа времени компиляции). Вместо обычного бинарного куска у нас появится экземпляр класса, который будет лопать память, просить время на конструктор / деструктор. Еще один кошмарик — вектор может пульнуть нам исключение. У него проверка выхода за границы включена всегда по стандарту и все тут. А мы свой assert() в релизной версии банально выключим флагом NDEBUG.

Есть еще один довод — а сможет ли GCC развернуть и векторизовать цикл, спрятанный внутри transform? Это нужно проверять отдельно.
Всего голосов 2: ↑1 и ↓10
итератор (который тоже придется писать)
Можно простые указатели возвращать, они вполне себе итераторы. Можно даже набыдлокодить и написать как-нибудь так:
std::transform(&lhs[0], &lhs[0] + Dim, &rhs[0], &lhs[0], std::minus<int>())
Комментарий пока не оценивали0
У нас внутри реализации квадратных скобок стоит assert. Взяв таким варварским способом указатель мы этот assert обойдем и будем лезть в массив бесконтрольно.

Кроме того, все это с треском развалится, как только мы вздумаем откомпилировать этот код для С++11.
Всего голосов 1: ↑0 и ↓1-1
Взяв таким варварским способом указатель мы этот assert обойдем и будем лезть в массив бесконтрольно.
Это не страшно, ведь у нас оба массива фиксированной длины Dim. Это, конечно, быдлокод, но только лишь потому, что мы вместо вызовов begin() и end() взяли и подставили их реализацию.
Комментарий пока не оценивали0
У него проверка выхода за границы включена всегда по стандарту и все тут

Нет. Проверка есть в функции at(), а в операторе [] никакой проверки нет.
Комментарий пока не оценивали0
Про стандарт я действительно погорячился. Наличие проверки в операторе [] зависит от реализации STL. Например, здесь пишут, что реализация STL в Visual Studio 2005 и 2008 делает эту проверку и для at() и для [].
Комментарий пока не оценивали0
У него проверка выхода за границы включена всегда по стандарту и все тут.

Ну просто юный недоумок!

Читай матчасть!
Всего голосов 2: ↑0 и ↓2-2
Согласно cppreference, lhs.begin() не может участвовать и как начало входного, и как начало выходного диапазона:
binary_op must not invalidate any iterators, including the end iterators, or modify any elements of the ranges involved.

Всего голосов 2: ↑1 и ↓10
Обратите внимание, там рядом пометка стоит, что эта гарантия требуется только с версии C++11, а мы работаем в рамках C++98, как бы печально это не было.

Да и вот пример на cplusplus.com:
Смотреть пример
// transform algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::transform
#include <vector>       // std::vector
#include <functional>   // std::plus

int op_increase (int i) { return ++i; }

int main () {
  std::vector<int> foo;
  std::vector<int> bar;

  // set some values:
  for (int i=1; i<6; i++)
    foo.push_back (i*10);                         // foo: 10 20 30 40 50

  bar.resize(foo.size());                         // allocate space

  std::transform (foo.begin(), foo.end(), bar.begin(), op_increase);
                                                  // bar: 11 21 31 41 51

  // std::plus adds together its two arguments:
  std::transform (foo.begin(), foo.end(), bar.begin(), foo.begin(), std::plus<int>());
                                                  // foo: 21 41 61 81 101

  std::cout << "foo contains:";
  for (std::vector<int>::iterator it=foo.begin(); it!=foo.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

Комментарий пока не оценивали0
Вы неправильно истолковали написанное, так сказано, что функциональный объект (std::minus<int>() в нашем случае) не имеет права менять объекты, а не то, что отрезки не могут перекрываться. Объект, собственно, ничего и не меняет, просто вычитает одно число из другого и выдает результат.
Всего голосов 1: ↑1 и ↓0+1
Спасибо за уточнение. Было бы очень хорошо, если бы вы привели дополнительный источник сведений по этому вопросу, потому как неясность действительно имеет место быть.
Комментарий пока не оценивали0
Нашел эту функцию в стандарте, там даже примечание для неё есть (25.3.4p5):
Remarks: result may be equal to first in case of unary transform, or to first1 or first2 in case of binary transform.
result в стандарте — это предпоследний параметр функции (итератор, по которому пишется ответ).
Всего голосов 1: ↑1 и ↓0+1
Большое спасибо.
Я пришел вот к какому выводу:
Наши реализации операций используют для доступа к массиву индексный оператор [].

Шаблон transform, в свою очередь, использует для доступа итератор. Это разные сущности.

Если некто сделает частичную специализацию нашего vec, и в ней перегрузит [], ваша идея со взятием указателей и передачей их в качестве итераторов сломает код — ведь квадратные скобки могут и не выдавать указатель на внутренний массив, а делать что-то свое. Не зря ведь вы написали, что это быдлокод.

Поэтому, чтобы вовсю использовать transform, мы обязаны требовать наличия в нашем векторе begin(), end() и итератора, а это дополнительный код, который нужен только для склейки с STL.

Несомненным плюсом использования transform является то, что код становится в некотором смысле более «функциональным», но это требует дополнительной работы.

И вопрос раскрутки цикла внутри transform и его векторизации остается открытым, но я думаю, с этим как раз проблем не будет.
Комментарий пока не оценивали0
дополнительный код, который нужен только для склейки с STL.
Там кода то на 4 строчки. А ещё это даст возможность использовать range-for пользователям С++11.
Всего голосов 2: ↑2 и ↓0+2
Будем обсуждать с haqreu этот вопрос. Еще раз спасибо за продуктивное обсуждение!
Комментарий пока не оценивали0
(опоздал с комментарием, ну и ладно)

std::minus<int> и не модифицирует диапазоны. Посмотрите пример по вашей ссылке, там как раз применяется toupper для in-place-модификации строки.
Всего голосов 2: ↑2 и ↓0+2
Согласен, в данном случае модифицирует не binary_op.

Позвольте тогда поинтересоваться, а если я напишу что-то в духе:

std::transform(V.begin(), V.end() - 1, V.begin() + 1, V.begin(), second_arg);


Где second_arg(a, b) — функция, всегда возвращающая b, тогда что произойдёт с V? В зависимости от порядка применения (слева-направо или справа-налево) вектор V = {1, 2, 3, 4, 5} может перейти либо в {2, 3, 4, 5, 5}, либо в {5, 5, 5, 5, 5}.

Меня слегка сбило с толку то, что в русской версии в разделе «требования» написано следующее:
Целью этих требований является возможность параллельных или неупорядоченных реализаций функции std::transform.


Казалось бы, это автоматически должно накладывать ограничение на то, что нельзя писать туда же, откуда читаются данные.
Комментарий пока не оценивали0
В зависимости от порядка применения
Порядок применения в общем случае фиксирован — с начала в конец. Требование на входные итераторы — InputIterator, это такая суровая штука, что когда вы переходите к следующему итератору, все предыдущие могут быть уже невалидны (хороший пример: итератор чтения из файла).
Комментарий пока не оценивали0
Так как сравнение с нулем обычно более эффективно, чем сравнение с определенным числом, то цикл с уменьшающимся счетчиком, как правило, выполняется быстрее.
— Этот совет несколько устарел.

Однако стоит также вспомнить, что в x86 действительно есть специальная инструкция loop, которая делает как раз то, что нужно:
— А это вообще антиоптимизация. На современных процессорах LOOP очень медленный по сравнению с наивным инкрементом, сравнением и переходом. Пример обсуждения на SO
Комментарий пока не оценивали0
Это затравка на будущую статью, которая обязательно когда-нибудь выйдет, как раз с указанием того, что многие советы из старых учебников уже никуда не годятся.
В данной статье никаких оптимизаций заведомо не делается

Спойлер к следующей статье
Например, при проходе по массиву задом наперед, GCC 4.9.2 наотрез отказывается делать векторизацию и все тут.
Комментарий пока не оценивали0
Появление этого цикла тесно связано с использованием size_t для индексации массивов.

Это же насколько феерическим дегенератом нужно быть, чтобы 1/2 статьи + 1/2 комментариев посвятить "гениальной догадке" индексировать циклы size_t ?!
Устроить из этой "мечты идиота" обсуждения на 2 страницы.
Всего голосов 3: ↑0 и ↓3-3
Я думаю в следующей статье будет показано что обход в обратном порядке быстрее, равно как и префиксная запись инкрементов/декрементов (хотя эти вопросы на хабре уже разбирались). И хотя это конечно от флагов оптимизации зависит и в релизе может не тормозить, отлаживать программу которая на несколько порядков медленнее просто из за того что было лень взять бумажку и проверить как то не приятно.
Всего голосов 2: ↑1 и ↓10
Вы верно догадались, нумерация по десятичным знакам числа Пи. Ход не очень оригинальный (о TeX уже упомянули), но это способ вместить практическую часть внутрь курса, а также показать, что эти статьи — отдельная сущность.
Всего голосов 1: ↑1 и ↓0+1
а также показать, что эти статьи — отдельная сущность.
Каким образом нумерация внутри цикла может показывать, что статьи не из цикла? Ваша статья сейчас называется «Краткий курс компьютерной графики». Про графику ни слова. Ну сделайте отдальный цикл статей.
Всего голосов 2: ↑2 и ↓0+2
После вашего разгромного комментария, я добавил в начало статьи (сразу после ката), огромное предупреждение. В нем указано, что все статьи с номерами 3.1, 3.14, 3.141 и далее по знакам числа Пи будут об аккуратной реализации теории на C++.
Комментарий пока не оценивали0
Извините, но
81.7144592952612 356384634040296077728271484375
81.7144592952612 498493181192316114902496337890

разница в 16ой значащей цифе — вполне соответствует точности типа double. Лишние знаки не несут смысла.
Я почти уверен, что подобрав другие числа можно получить контрпример, когда умножение на обратный дает бОльшую точность, чем деление. Выразить деление через умножение на 1/x — это способ избежать дублирования кода.

И последнее — проводились ли какие-нибудь сравнения с существующими библиотеками линейной алгебры для графики? Советую обратить внимание на вот этот тред на SO
Всего голосов 2: ↑2 и ↓0+2
Чисто математически, выполнение последовательных операций всегда приводит только к накоплению погрешности — с каждой новой операцией мы теряем информацию о младших разрядах.

Избежав дублирования кода, мы заменяем одно округление(деление) на округление(умножение(округление(деление))).

Таким образом, мы лишний раз потеряем информацию о знаках на округлении, да еще и выполним дополнительное умножение, что несколько замедлит код. Нет, компилятор это не выбросит (ну, его можно заставить при помощи --ffast-math, но для математического кода это очень опасный флаг).

В общем случае, правило работы с плавающей точкой такое — по возможности не делать лишних операций, даже если математически они эквивалентны.

Ко второму вопросу:
Мы пишем нашу библиотеку строго под нашу учебную задачу «построить миниатюрный отрисовщик, который будет собираться даже компилятором 15 летней давности».

По этому критерию все эти, несомненно хорошие, библиотеки нам не подходят — ученикам придется еще и разбираться с тем, как привинтить в их среде стороннюю библиотеку. А если это компьютер в университете, да без прав администратора, без доступа к конфигурации IDE — мало чего у них получится.

Если речь идет о «погонять в догонялки», я думаю, ATLAS или viennaCL уделают мой код, даже откомпилированный с -O3 -mavx и так далее. А может, и не уделают. Про это будет отдельная статья.

Здесь можно выделить еще один аспект — очень общий — при академическом обучении программированию нужно показать, «как скомпоновать программу из библиотек», или же, «как написать свою библиотеку»?

Дело в том, что наличие академического образования подразумевает, что выпускник не только может использовать черные ящики-библиотеки, но и может подробно (не фразой «Погугли!») разъяснить полному валенку, как внутри все устроено. А если может разъяснить, значит и свое может написать (потому как написание программы, это и есть разъяснение совершенно безмозглому валенку — компьютеру, чего от него хотят).

Отдельный вопрос, что на рынке труда такой выпускник (способный в запертой комнате без интернета с голым linux и i386 написать quake за лето) маловостребован. Потому как востребован тот, кто склепает это же за неделю из готовых запчастей по ставке $1 в час.
Всего голосов 1: ↑1 и ↓0+1
Операция «проектирования вектора», судя по контексту, это всё-таки операция «проецирования». Операция «погружения вектора в пространство большей размерности», это просто «изменение размерности вектора», или, если совсем упрощать, изменение размера вектора (по аналогии с классами контейнеров), но «размерность» тут (в контексте графики), наверное, подходит больше.
Комментарий пока не оценивали0
«Проектирование вектора» — термин из проективной геометрии. Мы из проективного пространства к 3D (координаты в таком пространстве — четырехмерные векторы) получаем представление вектора в «обычном» (Евклидовом) пространстве 3D (координаты — трехмерные векторы).

Ровно как и «погружение вектора» — когда в геометрии объект меньшей размерности помещают в пространство большей размерности, говорят именно о «погружении». Есть даже раздел такой «Дифференциальная геометрия погруженных многообразий».

Мы стараемся построить язык именно геометрических терминов, а не «программистских» операций с массивами координат.
Комментарий пока не оценивали0
а мы работаем в рамках C++98, как бы печально это не было.

Печально не это.
Печально, что помещаются такие статьи — полное говно, когда по ходу комментирвания выявляются одна ошибка автора за другой, полное невежество автора в том, о чем он рассуждает, а он только повторяет как попка-дурак: "да, вы правы, я оставлю это на дальнейшую проработку".

Позор Хабрахабру за такие публикации.
И позор коллегам gbg, на которых он постоянно ссылается поимённо, что они просмотрели публикацию такого убожества! Этих он ославил на славу.

Данная статья написана в тесном сотрудничестве

Не дай вам Бог таких друзей!
Всего голосов 2: ↑0 и ↓2-2
Бога нет.
Всего голосов 1: ↑1 и ↓0+1
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Показать лучшие за всё время

Истории

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2024, Habr