Jak zoptymalizować modyfikację komórki pamięci z carry?

Thread View: pl.comp.lang.c

2 messages

[T] Back to Threads [V] Tree View [G] Group Articles

2 total messages Started by Borneq Mon, 11 Nov 2019 18:37

#309968

Author: Borneq
Date: Mon, 11 Nov 2019 18:37

58 lines
3134 bytes

Sercem procedury mnożenia zwykłego(mpn_mul_basecase) w GMP jest 
mpir_addmul_1
MPIR jest wysoce zoptymalizowane i działa pod Visualem C++. W MPIR są 
dostarczone kody asemblerowe pod różne procesory.
Nie za bardzo lubię asemblera, trudno konfigurowalne, różne dla 
procesora, kompilatora, trybut 32/64 bitów itd.
I dla dzisiejszych procesorów trudno coś ręcznie zoptymalizować w 
assemblerze, zwłaszcza gdy nie ma SSE.
Jednak mpir_addmul_1 w assemblerze jest 2 razy szybszy!
W C:(usuwając nieistotne)
mp_limb_t addmul_1(mp_ptr rp, mp_srcptr up, mp_size_t n, mp_limb_t vl)
{
	mp_limb_t ul, cl, hpl, lpl, rl;
	cl = 0;
	do
	{
		ul = *up++;
		umul_ppmm(hpl, lpl, ul, vl);
		lpl += cl;
		cl = (lpl < cl) + hpl;
		rl = *rp;
		lpl = rl + lpl;
		cl += lpl < rl;
		*rp++ = lpl;
	} while (--n != 0);
	return cl;
}

gdzie długie mnożenie jest w umul_ppmm:
#    define umul_ppmm(xh, xl, m0, m1)       \
      do  {                                  \
            xl = _umul128( (m0), (m1), &xh); \
          } while (0)

a dla GCC po prostu:
          do  {                                  \
         mp_limb_double_t w = (mp_limb_double_t)x * y; \
         r_lo = (mp_limb_t)w;                             \
         r_hi = (mp_limb_t)(w >> GMP_LIMB_BITS);                     \
     } while (0)
bo ma tam typ 128 bitowy

JEDNAK
spowolnienie nie jest związane z tym mnożeniem, w asm jest podobnie choć 
używa mulx zamiast mul, który nie ustawia flag, w VC++ też można użyć 
zamiast _umul128 w razie konieczności.
JEDNAK
związane jest z tym że dostęp do pamięci jest wolniejszy niż do 
rejestrów, i trzeba dostać się dwukrotnie:
rl = *rp
*rp++
Można od razu przy jednym dostępie zwiększać o lpl, jednak dochodzi 
Carry. Carry można ustawić przez rzutowanie wyniku porównania na liczbę, 
wtedy nie generuje skoków.
PYTANIE: czy można modyfikować tylko rejestry, a potem zwiększyć tylko 
odpowiednio *rp ? Ale wtedy jak odczytać carry? W assemblerze można, 
natomiast tutaj jedyną metodą jest sprawdzenie czy wynik jest mniejszy 
niż którykolwiek składnik sumy (koniecznie dwóch a nie większej ilości)

Re: Jak zoptymalizować modyfikację komórki pamięci z carry?

#309969

Author: Borneq
Date: Mon, 11 Nov 2019 18:47

29 lines
2143 bytes

W dniu 11.11.2019 o 19:37, Borneq pisze:
> mp_limb_t addmul_1(mp_ptr rp, mp_srcptr up, mp_size_t n, mp_limb_t vl)
> {
>      mp_limb_t ul, cl, hpl, lpl, rl;
>      cl = 0;
>      do
>      {
>          ul = *up++;
>          umul_ppmm(hpl, lpl, ul, vl);
>          lpl += cl;
>          cl = (lpl < cl) + hpl;
>          rl = *rp;
>          lpl = rl + lpl;
>          cl += lpl < rl;
>          *rp++ = lpl;
>      } while (--n != 0);
>      return cl;
> }
> 

> PYTANIE: czy można modyfikować tylko rejestry, a potem zwiększyć tylko 
> odpowiednio *rp ? Ale wtedy jak odczytać carry? W assemblerze można, 
> natomiast tutaj jedyną metodą jest sprawdzenie czy wynik jest mniejszy 
> niż którykolwiek składnik sumy (koniecznie dwóch a nie większej ilości)

A może _addcarry_u64?
Nie tylko zwraca carry ale od razu dodaje poprzednie carry?
https://stackoverflow.com/questions/9145644/visual-c-x64-add-with-carry
https://scc.ustc.edu.cn/zlsc/tc4600/intel/2015.1.133/compiler_c/GUID-93E27B31-FDA6-4026-A2C4-98BF238349E9.htm

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads