Pull to refresh
31
0
Станислав Подгорский @entomolog

Пользователь

Send message
А чем вас потребность в " Lock-Modify-Unlock" так удивляет? Очень часто в репозитории приходится хранить не только текстовые файлы. Вот вам реальный пример из жизни: исходники флэша (.fla), текстуры (psd, tga), файлы 3ds max'а и еще куча всего остального. Поставил лок на файл, и спокойно его редактируешь и не волнуешься, что придется делать заново потому что кто-то успел закоммитить раньше.
Рассмотрим простейший кубический алгоритм перемножения матриц. Пожалуй, его знает любой студент или даже школьник.

Видимо не все так просто. У вас там ошибка. Я понимаю, что статья не про это, но странно видеть одну и ту же элементарную ошибку в каждом листинге статьи.

Поправьте пожалуйста, а то копипастят же!

При перемножении матрицы A размерностью mxn и матрицы B размерностью nxk, должна получаться матрица C размерностью mxk. Ваш алгоритм будет работать корректно только для квадратных матриц.

Детали тут
То, что там так сказано, не значит, что так оно и есть. В той статье есть комментарий по этому поводу.

Дело в том, что column-wise ни чем не лучше row-wise, это абсолютно симметричные способы хранения матриц. Поэтому column-wise не может быть лучше или хуже для перемножения.
Для нематематических приложений, row-wise удобнее, для математических column-wise удобнее.

Мысль, которую я пытался донести, это то, что это никакая не «особенность Java». И в Fortran проблема будет точно такая же. Не во всех ЯП есть многомерные массивы, вот в С/C++ нет. Но сам факт того, что двумерный массив хранится в линейном адрессном пространстве, вызывает cache miss при перемножении, и неважно как мы выбрали хранить массивы column-wise или row-wise.

Посмотрите на тело самого внутреннего цикла:

C[i][j] += A[i][k] * B[k][j];


Здесь, внутренний цикл инкрементирует переменную k. Доступ к элементам матрицы A не вызывает cache miss, так как A[i][k] и A[i][k+1] находятся «рядом», но есть проблема с B, так как элементы B[k][j] и B[k+1][j] находятся «далеко». Поэтому трансонирование матрицы B так сильно улучшает результат.

Теперь представим, что у нас Fortran, и матрицы хранятся column-wise. В этом случае элементы B[k][j] и B[k+1][j] находятся «рядом» и матрицу B транспонировать не нужно, однако A[i][k] и A[i][k+1] находятся «далеко» и теперь уже доступ к ним будет вызывать cache miss. Теперь транспонировать нужно матрицу A.

Что мы выиграли заменив row-wise на column-wise? Ничего.

P.S.
P.S. «magic» я упомянул с иронией, не более
Я понял вашу иронию, cache miss для меня никак не «magic», а объективная реальность, а вот загадочная «особенность Java» о которой вы говорили, как раз «magic».

У вас в простейшем кубическом методе перемножения ошибка.

При перемножении матрицы A размерностью mxn и матрицы B размерностью nxk, должна получаться матрица C размерностью mxk. Ваш алгоритм будет работать корректно только для квадратных матриц.

Ваш код:

for (int i = 0; i < A.rows(); i++) {
    for (int j = 0; j < A.columns(); j++) {
	for (int k = 0; k < B.columns(); k++) {
	    C[i][j] += A[i][k] * B[k][j];
	}
    }
}


Если A.columns() > A.rows(), то будет выход за пределы индексов С (если конечно вы создали матрицу С правильно размера). И в самом внутреннем цикле, граница также неправильная.

По идее, должно быть что-то вроде:

for (int i = 0; i < A.rows(); i++) {
    for (int j = 0; j < B.columns(); j++) {
	for (int k = 0; k < A.columns(); k++) {
	    C[i][j] += A[i][k] * B[k][j];
	}
    }
}


Ну и конечно где-то выше должна быть проверка, что A.columns() == B.rows(), но положим, что проверку мы здесь опускаем.

P.S. Я понимаю, что это было взято из другой статьи, но там хватает неточностей.
Траспонирование — это не какой-то magic. Оно нужно сугубо для Java, это её особенность чтения массивов. На других языках (например: Fortran) вообще не потребуется никого траспонировать.

Deosis правильно написал, что транспонирование позволяет эффективнее использовать кэш, а вы говорите про какой-то «magic». Это не особенность Java, это особенность хранения двумерного массива в линейном адрессном пространстве. И в Fortran будет то-же самое, с той лишь разницей, что транспонирование там нужно будет делать иначе, так как двумерные массивы там хранятся column-wise, а не row-wise как в большинстве языков, где есть двумерные массивы.
Спасибо за ссылку
Да, когда в качестве аргументов используются константы, все кончено оптимизируется на ура и компилятор просто вычисляет сумму заранее. Попробовал второй вариант, где аргументы приходят из вне, вот тут интереснее:
Вот такой код
struct foo
{
	int get_sum(const float* input, int size)
	{
		sum = 0; // try uncomment this
		
		for (int i = 0; i < size; ++i)
		{
			sum += input[i];
		}
      
		return sum;
	};
	
	float sum;
};

foo* get_foo();
float* get_floats();

int main(int argc, char** argv) {  
    float* floats = get_floats();
    foo* foo = get_foo();
    
    return foo->get_sum(floats, 10);
}


Компилируется вот в это
main:                                   # @main
        push    esi
        sub     esp, 8
        call    get_floats()
        mov     esi, eax
        call    get_foo()
        mov     dword ptr [eax], 0
        xorps   xmm0, xmm0				;sum = 0; 
        addss   xmm0, dword ptr [esi]			;sum += input[0];
        movss   dword ptr [eax], xmm0			;ненужный store sum
        addss   xmm0, dword ptr [esi + 4]		;sum += input[1];
        movss   dword ptr [eax], xmm0			;ненужный store sum
        addss   xmm0, dword ptr [esi + 8]		;sum += input[2];
        movss   dword ptr [eax], xmm0			;ненужный store sum
        addss   xmm0, dword ptr [esi + 12]		;sum += input[3];
        movss   dword ptr [eax], xmm0			;ненужный store sum
        addss   xmm0, dword ptr [esi + 16]		;sum += input[4];
        movss   dword ptr [eax], xmm0			;ненужный store sum
        addss   xmm0, dword ptr [esi + 20]		;sum += input[5];
        movss   dword ptr [eax], xmm0			;ненужный store sum
        addss   xmm0, dword ptr [esi + 24]		;sum += input[6];
        movss   dword ptr [eax], xmm0			;ненужный store sum
        addss   xmm0, dword ptr [esi + 28]		;sum += input[7];
        movss   dword ptr [eax], xmm0			;ненужный store sum
        addss   xmm0, dword ptr [esi + 32]		;sum += input[8];
        movss   dword ptr [eax], xmm0			;ненужный store sum
        addss   xmm0, dword ptr [esi + 36]		;sum += input[9];
        movss   dword ptr [eax], xmm0
        cvttss2si       eax, xmm0
        add     esp, 8
        pop     esi
        ret





Да, компилятор развернул цикл, но нагенерил кучу ненужных инструкций, потому что предпологает что член класса sum может иметь aliasing с input.

По сути код выше можно упростить до

этого
main:                                   # @main
        push    esi
        sub     esp, 8
        call    get_floats()
        mov     esi, eax
        call    get_foo()
        mov     dword ptr [eax], 0
        xorps   xmm0, xmm0			;sum = 0; 
        addss   xmm0, dword ptr [esi]		;sum += input[i];
        addss   xmm0, dword ptr [esi + 4]
        addss   xmm0, dword ptr [esi + 8]
        addss   xmm0, dword ptr [esi + 12]
        addss   xmm0, dword ptr [esi + 16]
        addss   xmm0, dword ptr [esi + 20]
        addss   xmm0, dword ptr [esi + 24]
        addss   xmm0, dword ptr [esi + 28]
        addss   xmm0, dword ptr [esi + 32]
        addss   xmm0, dword ptr [esi + 36]
        movss   dword ptr [eax], xmm0		;сохраняем sum
        cvttss2si       eax, xmm0
        add     esp, 8
        pop     esi
        ret



Но вот если исходный код поменять на:
struct foo
{
	 int get_sum(const float* input, int size)
	 {
	 	 float _sum = 0;
     
		 for (int i = 0; i < size; ++i)
	 	 {
	 	 	 _sum += input[i];
	 	 }
      
	 	 sum = _sum;
      
	 	 return sum;
	};
	
	float sum;
};


То все ненужные инструкции пропадают, и получается в точности то что в упрощенном варианте.

Тот же эффект достигается, если поставить

__restrict
struct foo
{
	int get_sum(const float* __restrict input, int size)
	{
        sum = 0;
     
        for (int i = 0; i < size; ++i)
		{
			sum += input[i];
		}
            
        return sum;
	};
	
	float sum;
};


результат
main:                                   # @main
        push    esi
        sub     esp, 8
        call    get_floats()
        mov     esi, eax
        call    get_foo()
        xorps   xmm0, xmm0
        addss   xmm0, dword ptr [esi]
        addss   xmm0, dword ptr [esi + 4]
        addss   xmm0, dword ptr [esi + 8]
        addss   xmm0, dword ptr [esi + 12]
        addss   xmm0, dword ptr [esi + 16]
        addss   xmm0, dword ptr [esi + 20]
        addss   xmm0, dword ptr [esi + 24]
        addss   xmm0, dword ptr [esi + 28]
        addss   xmm0, dword ptr [esi + 32]
        addss   xmm0, dword ptr [esi + 36]
        movss   dword ptr [eax], xmm0
        cvttss2si       eax, xmm0
        add     esp, 8
        pop     esi
        ret



Получается, что запись в члены класса, по сути эквивалентна к out параметру и может приводить к aliasing c входными данными. Если запись результата как out параметр штука редкая, и в основном не приветствуется, то изменение членов класса происходит крайне часто.

Поэтому чтобы не гадать что оно там получится, мне проще в tight loop'ах просто все члены класса которые будут использоваться в цикле, скопировать в локальные переменные, а затем по выходу из цикла нужные скопировать обратно. Ну или restrict поставить. Конечно это только про tight loop'ы

В данном примере, с get_floats() и get_foo() у компилятора нет ни малейшого шанса что либо проверить, поэтому предпологается худший вариант. Что будет происходить в реальном случае я без понятия. Может компилятор сможет отследить все вызовы и все таки догадается, что там нету aliasing? А что если там полиморфизм замешан, и таблица указателей на виртуальные функции, что тогда?

С преждевременной оптимизацией понятно. Просто бывает так, что 98% времени работы алгоритма упирается к каких-то 5 строчек кода, и возникает желание выжать из них все что можно.
Не совсем по теме strict aliasing, но все же. Насколько умным компилятор может быть, чтобы вывести что указатели не имеют aliasing?

Дело в том, что имею такую привычку, когда все возможные оптимизации в tight loop'е заканчиваются, лепить restrict везде, где только можно. Не редко неплохо помогает. Хотелось бы знать кейсы где этого делать нету необходимости, а где все же желательно.

Вот например, представим такой класс:

struct bar
{
	int Summation(const float* input, int n)
	{
		sum = 0;
		for (int i = 0; i < n; ++i)
		{
			sum += input[i];
		}
	};
	
	float sum;
}


С одной стороны здесь нету out параметра и все хорошо, но с другой стороны, обращение к sum происходит через указатель this и компилятору никто не дает гарантий что указатель на sum не будет иметь aliasing с input.

По сути, компилятор будет вынужден на каждом прибавлении к sum делать store.

Я как то наблюдал aliasing в этом случае с MSVC, с тех пор, предпочитаю в случае с tight loop'fми копировать содержимое членов класса в локальные переменные перед входом в цикл, а затем копировать обратно после выхода.

Но это в случае с MSVC, где нету strict aliasing. Что будет делать в этом случае LLVM?

Или другой пример:

struct bar
{
	int Summation(const float* input, int n)
	{
		*sum = 0;
		for (int i = 0; i < n; ++i)
		{
			*sum += input[i];
		}
	};
	
	bar()
	{
		sum = new float;
	};
	
	~bar()
	{
		delete sum;
	};
	
private:	
	float* sum;
}


В этом случае, компилятор мог бы вывести, что указатель sum не может иметь aliasing с input. Указатель sum в приватной секции и мы аллокейтим память, которая априори не может пересечся с input. Поэтому кажется, что компилятор может опустить store в *sum внутри цикла, а сделать store только по выходу.
Но что-то не уверен компилятор может так рассуждать. В конце концов мы могли перегрузить new, нужно еще запретить копирование, да и приватная секция ничего не значит, мы могли бы положить туда указатель на любой участок памяти.

Вопрос в том, что действительно все так плохо и пару лишних restrict + копирование в локальные переменные не помешают, или это паранойя?

Спасибо.
Напомнило Line Scan Camera от Elm Chan.
Пару картинок
поезд:
image
кукла:
image
Спасибо! Я когда-то давно взял готовый рецепт, но не понял как оно работает, а тут вы все подробно расписали, спасибо!
Для отрисовки каждого пикселя растеризатор нам даёт барицентрические координаты пикселя (альфа, бета, гамма). Это означает, что текущий пиксель имеет пространственные координаты p = альфа p0 + бета p1 + гамма p2. Мы интерполируем текстурные координаты ровно так же, затем интерполируем и вектор нормали:
Если я правильно понимаю, то линейно интерполировать текстурные координаты и нормали после проецирования (а раз речь идет о растеризаторе, то получается после) можно только в случае ортогональной проекции. Правильно?
В случае с перспективной проекцией, там будут искажения. Я когда-то очень давно писал свой софтовый рендер и уперся в эту проблему. Несколько дней дебажил, думал что проблема в коде, а оказалась — в математике.
Забавно то, что на моем Asus A686 (Windows Mobile 5.0) по какой-то причине растеризатор как раз не учитывал перспективные искажения, получались точно такие же забавные артефакты.
Спасибо, позновательно!
На тему бесконечности, когда-то игрался с raymarching, из простейшей геометрии можно создавать "бесконечные" сцены: немного бесконечности
Мне вот интересно, имеет ли какое-то косвенное отношение рассмотренный вами подход к новомодному методу уменьшения переобучения, так называемому dropout.
Метод впервые был описан (насколько мне известно) в ImageNet Classification with Deep Convolutional Neural Networks. Alex Krizhevsky Ilya Sutskever Geoffrey E. Hinton
Но метод никак, кроме как на интуиции не обоснован. Суть примерно такая: а давайте с вероятностью 0.5 процентов будем выключать нейроны, чтобы они не расслаблялись и не начинали запоминать датасет.
Я помню (лет десять назад это было), если надо быстро что-то смакетировать, брал AVR-ку, и прямо к DIP корпусу тоненькими проводками припаивал питание и «программатор», который представлял собой ничто иное как 5 проводков припаянных к LPT. Далее в зависимости от потребностей макета, припаивал светодиод/реле/пищалку. В итоге, на это времени уходило меньше пяти минут. Если нужно что-то сложнее, то без разводки платы тут никак.
Гораздо больше проблем с софтом было. Начинал я с wavrasm + PonyProg. Потом, когда освоил C, переполз на AtmelStudio + WinAVR, но прошивал по прежнему PonyProg'ом (почему не помню). Неправильными фьюзами я попортил несчетное колличество кристалов.
Для старта, от более простой среды я в то время не отказался бы.
Я никогда не интересовался как происходит процесс взлома, и какие есть средства защиты от этого, но я всегда удивлялся, как до сих пор люди умудряются ломать софт. Кто то может объяснить почему нельзя сделать такую защиту, взлом которой был бы настолько трудоемок, что был бы не под силу таким вот группам, как упомянутая в статье 3DM?
Вообще я всегда думал, что игры можно сломать, только по той причине, что хорошую защиту не делают специально.
Проект не open source, да? Если open source, было бы очень интересно попробовать.
При вызове фрагментого шейдера для конкретной точки, значения varying переменных линейно интерполируются между вершинами треугольника, которому принадлежит данная точка.
На мой взгляд, вы тут немного вводите в заблуждение читателей. В вашем конкретном примере с плоским треугольником — да, так и есть, линейно. Но в общем случае, они интерполируются не линейно, даже в вашем следующем примере с кубиком, там уже нету линейной интерполяции.

Большинство руководств или статей перепрыгивают сразу на использование какой-нибудь библиотеки.
Если цель не поиграться, а сделать продукт, то это весьма правильное решение.

Если вы думаете, что WebGL рисует 3D, вы ошибаетесь. WebGL ничего не знает о 3D, это скорее низкоуровневый 2D API, и всё что он умеет делать, это рисовать треугольники.
Посыл правильный, но вы немного перегнули палку :).

Как по мне, если интерес представляет именно работа с графическим АПИ, то WebGL в принципе тот-же OpenGL ES 2.0, и является урезанной десктопной версией. Рассматривать WebGL как самостоятельную сущность, о которой нет документации и статей, это перегиб. Они просто не нужны, так как есть огромное число разных туториалов по OpenGL ES и OpenGL 4.*.

В контексте Web'а, как по мне интереснее рассмотреть немного более практические примеры с использованием графических библиотек. Ведь, писать все с нуля, не имеет смысла. Точно так же как никто не пишет игры на чистом OpenGL, так же и WebGL не для этого.

Статья хорошая, для людей, интересующихся этой темой, думаю создаст правильное представление о WebGL.
У меня что-то с GL_LINES никогда проблем не было (ну кроме как толщина не везде работает). А вот GL_POINTS да, зачастую не работают.
Да вобщем-то GL_LINES и GL_POINTS не особо то и нужны, разве что для дебага.
Вот так оно выглядит


Скринов с сравнениями с полупрозрачным плэйником у меня к сожалению не осталось, но думаю понятно как выглядит белое пятно.
Такая штука вообще достаточно спорная, не везде хорошо работает.
Хотелось бы больше деталей про фары машин и их отражения на асфальте, но это уже к автору, а не к переводчику. А перевод отличный!

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

Даже если шейдинг не отложенный, есть один грязный способ получить отдаленно похожий эффект.
Когда-то я возился с светом фар, на проекте они были сделаны просто плэйниками с альфой, т.е. поверх кадра просто накладывается белая полупрозрачная текстура. Выглядит ужасно, т.к. такой свет ничего не освещает, а просто подмешивает больше «белого».
У меня возникла идея умножать значение в буфере на некую величину, тем самым как-бы увеличивая освещенность. На первый взгляд, может показаться, что тут без постэффекта никак, но есть один хитрый способ это сделать, с помощью блэндинга:

  • BlendEquation: GL_FUNC_ADD
  • source: GL_DST_COLOR
  • destination: GL_ONE

В итоге мы имеем, что:
destinationColor = destinationColor + destinationColor * sourceColor
Теперь, если в текстуру запечь фейковое освещение, то оно будет как бы «добавляться» в уже отрендренную сцену.

Есть еще замечательный extension: EXT_shader_framebuffer_fetch, который позволяет читать из текущего фреймбуфера в пиксельном шейдере. С помощью него обычно реализуют программный блэндинг и различные простые постэффекты, которые получаются очень дешевыми, так как не нужно переключать рендертаргет. Использую этот extension можно реализовать различные схемы такого фейкового освещения.
А вы не задумывались, почему на Фортране? Что есть Фортран и для чего он был создан?

Уточню, в книге пример приведен на очень старом диалекте фортрана — FORTRAN 66. Более того, тот пример намного боле громоздкий и трудно читаем.

Вообще тема фортрана уже настолько избита и не раз поднималась на хабре, что обсуждать ее еще раз, ну не знаю.
Основные причины почему он до сих пор востребован(и скорее всего еще долго будет) это:
  • Наличие большого числа очень сложного софта, работа которого проверена временем.
  • Наличие большого числа талантливых людей, для которых фортран является основным языком.
  • Для людей науки, которые не связаны с программирование, фортран проще в освоении.
  • Скорость фортрана на уровне C/C++ (что весьма не плохо).


То, что фортран производительнее C/C++ — это уже давно не правда.
На мой взгляд, код на С++ получается(при использовании соответствующих инструментов) намного выразительнее и компактнее.

В фортране нету шаблонов, на мой взгляд это существенный минус.
Приведу не слишком очевидный пример(очевидные и так понятны), есть такая штука как Symbolic Pre-computation for Numerical Applications, SEMT. Позволяет делать просто потрясающую вещь, можно записать функции формы для элементов высокого порядка и не брать большое число частных производных вручную(или с помощью стороннего инструмента).
1

Information

Rating
Does not participate
Location
Morgantown, West Virginia, США
Date of birth
Registered
Activity