Реализация интерполяции

[Maxi]

Интерполяцию кстати... смотрю и плачу.
Думали о каких то решениях "не тупо в лоб"?

вообще в ercos 2d-3d lookup вставкой на ассемблере сделан.

[AndreyB]

Интерполяцию кстати... смотрю и плачу.
Думали о каких то решениях "не тупо в лоб"?

вообще в ercos 2d-3d lookup вставкой на ассемблере сделан.

При всём моём уважении, я не могу декодировать мысль из этого эмоционального комментария.
Буду рад мыслями, идеям и предложениями. Конечно особенно буду рад в виде патча, но и конструктивная критика тоже будет радовать.

[nikll]

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

[Maxi]

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

пока таблиц две конечно не критична. А потом это будут самые вызываемые процедуры.

[nikll]

Ну да я именно это и имел ввиду. Функции интерполяции подлежат первоочередной оптимизации, но пока ресурсов хватает заморачиватся рано.

[Sergey89]

В open5xxxecu кстати поиск индекса в table_lookup функции сделан через бинарный поиск. Можно ещё подумать на тему того, чтобы запоминать последний найденный индекс и новый поиск начинать от его.

[AndreyB]

В open5xxxecu кстати поиск индекса в table_lookup функции сделан через бинарный поиск. Можно ещё подумать на тему того, чтобы запоминать последний найденный индекс и новый поиск начинать от его.

Приму в дар патч для функции бинарного поиска - это в файле engine_math.c

Запоминание последнего индекса кстати может оказаться эффективнее бинарного поиска по скорости! Но нужно будет аккуратно где-то хранить прошлый индекс. А совместить бинарный поиск и последний индекс наверное не получится.

[Sergey89]

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

Вообщем я потестирую разные способы оптимизации и накатаю патч.

[AndreyB]

Вообщем я потестирую разные способы оптимизации и накатаю патч.

Завёл тикет #9 - мне нужен твой логин на sourceforge тогда могу тикет на тебя повесить.

[mpro]

Вообщем я потестирую разные способы оптимизации и накатаю патч.

Завёл тикет #9 - мне нужен твой логин на sourceforge тогда могу тикет на тебя повесить.

Заранее прошу прощения, но все оси у карт настройки имеют (A + n*B), зачем вообще искать по ним? (Из тех, что я видел при настройке)
1 сложение + 1 умножение. (Хотя я не знаю скорость выполнения операций умножения на данном контролере)
Если используется линейная интерполяция, то можно неравномерную карту подогнать к равномерному виду на PC перед заливкой.
Я чего-то не понимаю?

[Sergey89]

Многие, но не все.

[AndreyB]

Заранее прошу прощения, но все оси у карт настройки имеют (A + n*B), зачем вообще искать по ним? (Из тех, что я видел при настройке)
1 сложение + 1 умножение. (Хотя я не знаю скорость выполнения операций умножения на данном контролере)

В принципе - да. Но с моей точки зрения это будет типичная экономия не по делу - процессор мощный, можно позволить себе сделать на 5% лучше в три раза медленне. На, будет в три раза медленнее - но зато будет на 5% лучше.

[AndreyB]

2d-3d lookup вставкой на ассемблере сделан.

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

Текущий C код

Code: Select all

/** @brief	Binary search
 * @returns	the highest index within sorted array such that array[i] is greater than or equal to the parameter
 * @note If the parameter is smaller than the first element of the array, -1 is returned.
 */
int findIndex(const float array[], int size, float value) {
	if (value < array[0])
		return -1;
	int middle;
	int left = 0;
	int right = size;
	// todo: extract binary search as template method?
	while (true) {
#if 0
		// that's an assertion to make sure we do not loop here
		size--;
		efiAssert(size > 0, "Unexpected state in binary search", 0);
#endif
		middle = (left + right) / 2;
		if (middle == left)
			break;
		if (value < array[middle]) {
			right = middle;
		} else if (value > array[middle]) {
			left = middle;
		} else {
			break;
		}
	}
	return middle;
}

компилятор делает из этого

Code: Select all

0801f1c4 <_Z9findIndexPKfif>:
 801f1c4:	b480      	push	{r7}
 801f1c6:	b089      	sub	sp, #36	; 0x24
 801f1c8:	af00      	add	r7, sp, #0
 801f1ca:	60f8      	str	r0, [r7, #12]
 801f1cc:	60b9      	str	r1, [r7, #8]
 801f1ce:	ed87 0a01 	vstr	s0, [r7, #4]
 801f1d2:	68fb      	ldr	r3, [r7, #12]
 801f1d4:	ed93 7a00 	vldr	s14, [r3]
 801f1d8:	edd7 7a01 	vldr	s15, [r7, #4]
 801f1dc:	eeb4 7ae7 	vcmpe.f32	s14, s15
 801f1e0:	eef1 fa10 	vmrs	APSR_nzcv, fpscr
 801f1e4:	dd02      	ble.n	801f1ec <_Z9findIndexPKfif+0x28>
 801f1e6:	f04f 33ff 	mov.w	r3, #4294967295
 801f1ea:	e031      	b.n	801f250 <_Z9findIndexPKfif+0x8c>
 801f1ec:	2300      	movs	r3, #0
 801f1ee:	61fb      	str	r3, [r7, #28]
 801f1f0:	68bb      	ldr	r3, [r7, #8]
 801f1f2:	61bb      	str	r3, [r7, #24]
 801f1f4:	69fa      	ldr	r2, [r7, #28]
 801f1f6:	69bb      	ldr	r3, [r7, #24]
 801f1f8:	4413      	add	r3, r2
 801f1fa:	0fda      	lsrs	r2, r3, #31
 801f1fc:	4413      	add	r3, r2
 801f1fe:	105b      	asrs	r3, r3, #1
 801f200:	617b      	str	r3, [r7, #20]
 801f202:	697a      	ldr	r2, [r7, #20]
 801f204:	69fb      	ldr	r3, [r7, #28]
 801f206:	429a      	cmp	r2, r3
 801f208:	d100      	bne.n	801f20c <_Z9findIndexPKfif+0x48>
 801f20a:	e020      	b.n	801f24e <_Z9findIndexPKfif+0x8a>
 801f20c:	697b      	ldr	r3, [r7, #20]
 801f20e:	009b      	lsls	r3, r3, #2
 801f210:	68fa      	ldr	r2, [r7, #12]
 801f212:	4413      	add	r3, r2
 801f214:	ed93 7a00 	vldr	s14, [r3]
 801f218:	edd7 7a01 	vldr	s15, [r7, #4]
 801f21c:	eeb4 7ae7 	vcmpe.f32	s14, s15
 801f220:	eef1 fa10 	vmrs	APSR_nzcv, fpscr
 801f224:	dd02      	ble.n	801f22c <_Z9findIndexPKfif+0x68>
 801f226:	697b      	ldr	r3, [r7, #20]
 801f228:	61bb      	str	r3, [r7, #24]
 801f22a:	e00f      	b.n	801f24c <_Z9findIndexPKfif+0x88>
 801f22c:	697b      	ldr	r3, [r7, #20]
 801f22e:	009b      	lsls	r3, r3, #2
 801f230:	68fa      	ldr	r2, [r7, #12]
 801f232:	4413      	add	r3, r2
 801f234:	ed93 7a00 	vldr	s14, [r3]
 801f238:	edd7 7a01 	vldr	s15, [r7, #4]
 801f23c:	eeb4 7ae7 	vcmpe.f32	s14, s15
 801f240:	eef1 fa10 	vmrs	APSR_nzcv, fpscr
 801f244:	d400      	bmi.n	801f248 <_Z9findIndexPKfif+0x84>
 801f246:	e002      	b.n	801f24e <_Z9findIndexPKfif+0x8a>
 801f248:	697b      	ldr	r3, [r7, #20]
 801f24a:	61fb      	str	r3, [r7, #28]
 801f24c:	e7d2      	b.n	801f1f4 <_Z9findIndexPKfif+0x30>
 801f24e:	697b      	ldr	r3, [r7, #20]
 801f250:	4618      	mov	r0, r3
 801f252:	3724      	adds	r7, #36	; 0x24
 801f254:	46bd      	mov	sp, r7
 801f256:	f85d 7b04 	ldr.w	r7, [sp], #4
 801f25a:	4770      	bx	lr