Es lo que hay pero por eso cuando se requiere incrementar el rendimiento se trabaja con algoritmos, estructuras de datos, el orden en que ponemos las instrucciones y el conocimiento de las herramientas que vamos a usar (por ejemplo el compilador, el lenguaje, el interprete, etc).
Hay aprovechar todo lo que nos permitan usar de una mejor forma lo que nos ofrece el sistema y eso es por lo general por software. Sin ir más lejos
No es lo mismo
a un
y mucho menos a un
for()
{
for()
{
for()
{
}
}
}
Imagina 3 for anidados en un procesador con pipeline.
No es lo mismo
a
struct {
char c;
char pad[x]
int i;
}
donde x es un valor que nos permite forzar que la estructura ocupe una línea entera de la caché, sobre todo cuando la estructura es compartida entre varios procesos.
Hay técnicas que se conocen como loop unrolling, por lo general cuando el compilador detecta que puede, por así decirlo desenrollar un loop, lo va a hacer para optimizar la ejecución, de acuerdo a la plataforma.
#include <stdio.h>
int main(int argc, char **argv)
{
int k = 0;
for( k = 0; k < 5; ++k )
{
volatile int temp = k;
}
}
0000000000400400 <main>:
400400: c7 44 24 fc 00 00 00 movl $0x0,-0x4(%rsp)
400407: 00
400408: c7 44 24 fc 01 00 00 movl $0x1,-0x4(%rsp)
40040f: 00
400410: c7 44 24 fc 02 00 00 movl $0x2,-0x4(%rsp)
400417: 00
400418: c7 44 24 fc 03 00 00 movl $0x3,-0x4(%rsp)
40041f: 00
400420: c7 44 24 fc 04 00 00 movl $0x4,-0x4(%rsp)
400427: 00
400428: c3 retq
En este caso, en el ARM Cortex M7, no tendría problemas en introducir dos instrucciones a la vez en el pipeline.
Si le aumentamos a iterar sobre 20 elementos
0000000000400400 <main>:
400400: 31 c0 xor %eax,%eax
400402: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1)
400408: 89 44 24 fc mov %eax,-0x4(%rsp)
40040c: 83 c0 01 add $0x1,%eax
40040f: 83 f8 14 cmp $0x14,%eax
400412: 75 f4 jne 400408 <main+0x8>
400414: f3 c3 repz retq
Pero le podemos ayudar un poco desenrollando el ciclo nosotros mismos.
#include <stdio.h>
volatile char temp0[20];
volatile int temp1[20];
int main(int argc, char **argv)
{
int k,i = 0;
for( k = 0; k < 10; ++k )
{
temp0[i] = k;
temp0[i+1] = k +1;
temp1[i] = k;
temp1[i+1] = k +1;
i = i +2;
}
}
0000000000400400 <main>:
400400: c6 05 59 0c 20 00 00 movb $0x0,0x200c59(%rip) # 601060 <temp0>
400407: c6 05 53 0c 20 00 01 movb $0x1,0x200c53(%rip) # 601061 <temp0+0x1>
40040e: c7 05 68 0c 20 00 00 movl $0x0,0x200c68(%rip) # 601080 <temp1>
400415: 00 00 00
400418: c7 05 62 0c 20 00 01 movl $0x1,0x200c62(%rip) # 601084 <temp1+0x4>
40041f: 00 00 00
400422: c6 05 39 0c 20 00 01 movb $0x1,0x200c39(%rip) # 601062 <temp0+0x2>
400429: c6 05 33 0c 20 00 02 movb $0x2,0x200c33(%rip) # 601063 <temp0+0x3>
400430: c7 05 4e 0c 20 00 01 movl $0x1,0x200c4e(%rip) # 601088 <temp1+0x8>
400437: 00 00 00
40043a: c7 05 48 0c 20 00 02 movl $0x2,0x200c48(%rip) # 60108c <temp1+0xc>
400441: 00 00 00
400444: c6 05 19 0c 20 00 02 movb $0x2,0x200c19(%rip) # 601064 <temp0+0x4>
40044b: c6 05 13 0c 20 00 03 movb $0x3,0x200c13(%rip) # 601065 <temp0+0x5>
400452: c7 05 34 0c 20 00 02 movl $0x2,0x200c34(%rip) # 601090 <temp1+0x10>
400459: 00 00 00
40045c: c7 05 2e 0c 20 00 03 movl $0x3,0x200c2e(%rip) # 601094 <temp1+0x14>
400463: 00 00 00
400466: c6 05 f9 0b 20 00 03 movb $0x3,0x200bf9(%rip) # 601066 <temp0+0x6>
40046d: c6 05 f3 0b 20 00 04 movb $0x4,0x200bf3(%rip) # 601067 <temp0+0x7>
400474: c7 05 1a 0c 20 00 03 movl $0x3,0x200c1a(%rip) # 601098 <temp1+0x18>
40047b: 00 00 00
40047e: c7 05 14 0c 20 00 04 movl $0x4,0x200c14(%rip) # 60109c <temp1+0x1c>
400485: 00 00 00
400488: c6 05 d9 0b 20 00 04 movb $0x4,0x200bd9(%rip) # 601068 <temp0+0x8>
40048f: c6 05 d3 0b 20 00 05 movb $0x5,0x200bd3(%rip) # 601069 <temp0+0x9>
400496: c7 05 00 0c 20 00 04 movl $0x4,0x200c00(%rip) # 6010a0 <temp1+0x20>
40049d: 00 00 00
4004a0: c7 05 fa 0b 20 00 05 movl $0x5,0x200bfa(%rip) # 6010a4 <temp1+0x24>
4004a7: 00 00 00
4004aa: c6 05 b9 0b 20 00 05 movb $0x5,0x200bb9(%rip) # 60106a <temp0+0xa>
4004b1: c6 05 b3 0b 20 00 06 movb $0x6,0x200bb3(%rip) # 60106b <temp0+0xb>
4004b8: c7 05 e6 0b 20 00 05 movl $0x5,0x200be6(%rip) # 6010a8 <temp1+0x28>
4004bf: 00 00 00
4004c2: c7 05 e0 0b 20 00 06 movl $0x6,0x200be0(%rip) # 6010ac <temp1+0x2c>
4004c9: 00 00 00
4004cc: c6 05 99 0b 20 00 06 movb $0x6,0x200b99(%rip) # 60106c <temp0+0xc>
4004d3: c6 05 93 0b 20 00 07 movb $0x7,0x200b93(%rip) # 60106d <temp0+0xd>
4004da: c7 05 cc 0b 20 00 06 movl $0x6,0x200bcc(%rip) # 6010b0 <temp1+0x30>
4004e1: 00 00 00
4004e4: c7 05 c6 0b 20 00 07 movl $0x7,0x200bc6(%rip) # 6010b4 <temp1+0x34>
4004eb: 00 00 00
4004ee: c6 05 79 0b 20 00 07 movb $0x7,0x200b79(%rip) # 60106e <temp0+0xe>
4004f5: c6 05 73 0b 20 00 08 movb $0x8,0x200b73(%rip) # 60106f <temp0+0xf>
4004fc: c7 05 b2 0b 20 00 07 movl $0x7,0x200bb2(%rip) # 6010b8 <temp1+0x38>
400503: 00 00 00
400506: c7 05 ac 0b 20 00 08 movl $0x8,0x200bac(%rip) # 6010bc <temp1+0x3c>
40050d: 00 00 00
400510: c6 05 59 0b 20 00 08 movb $0x8,0x200b59(%rip) # 601070 <temp0+0x10>
400517: c6 05 53 0b 20 00 09 movb $0x9,0x200b53(%rip) # 601071 <temp0+0x11>
40051e: c7 05 98 0b 20 00 08 movl $0x8,0x200b98(%rip) # 6010c0 <temp1+0x40>
400525: 00 00 00
400528: c7 05 92 0b 20 00 09 movl $0x9,0x200b92(%rip) # 6010c4 <temp1+0x44>
40052f: 00 00 00
400532: c6 05 39 0b 20 00 09 movb $0x9,0x200b39(%rip) # 601072 <temp0+0x12>
400539: c6 05 33 0b 20 00 0a movb $0xa,0x200b33(%rip) # 601073 <temp0+0x13>
400540: c7 05 7e 0b 20 00 09 movl $0x9,0x200b7e(%rip) # 6010c8 <temp1+0x48>
400547: 00 00 00
40054a: c7 05 78 0b 20 00 0a movl $0xa,0x200b78(%rip) # 6010cc <temp1+0x4c>
400551: 00 00 00
400554: c3 retq
Ahí es donde entra nuestra capacidad de entender nuestro algoritmo y la arquitectura en la que estamos trabajando para incrementar el rendimiento en caso de necesitarlo. Si no hay necesidad, pues el rendimiento que obtenemos al incrementar la frecuencia de reloj podría ser más que suficiente.
En linux tenemos varias herramientas para perfilar el comportamiento de los programas, además que hay ciertos registros en la CPU que mantienen la información sobre eventos como cache load, cache miss, branch miss, entre otros.
Algunas de estas herramientas son
- perf que pertenece al kernel de linux
- oprofile
- papi
- cachegrind
Por ejemplo con perf vamos perfilar el comando sleep
sudo perf stat -a -B -e cache-references,cache-misses,cycles,instructions,branches,branch-misses,stalled-cycles-frontend,stalled-cycles-backend,faults,migrations,L1-dcache-loads,L1-dcache-load-misses,LLC-loads,LLC-load-misses sleep 5
Performance counter stats for 'system wide':
1 867 573 612 cache-references [33.35%]
3 945 227 cache-misses # 0.211 % of all cache refs [33.43%]
5 881 494 734 cycles [33.46%]
7 516 215 308 instructions # 1.28 insns per cycle
# 0.02 stalled cycles per insn [33.46%]
1 870 488 999 branches [33.38%]
2 211 585 branch-misses # 0.12% of all branches [33.30%]
154 909 407 stalled-cycles-frontend # 2.63% frontend cycles idle [33.27%]
106 690 388 stalled-cycles-backend # 1.81% backend cycles idle [33.27%]
453 faults [100.00%]
0 migrations
1 850 876 631 L1-dcache-loads [33.27%]
1 849 926 L1-dcache-load-misses # 0.10% of all L1-dcache hits [33.27%]
7 101 574 LLC-loads [33.27%]
2 079 920 LLC-load-misses # 29.29% of all LL-cache hits [33.27%]
5.001107881 seconds time elapsed
Ahora voy a obtener los valores del siguiente script en python
from xml.dom.minidom import parse, parseString
from lxml import etree as ET
dom = parse("cadena.xml")
print("-------------------------")
for node in dom.getElementsByTagName("cfdi:Impuestos"):
print(node.getAttribute("TotalImpuestosTrasladados"))
#Con lxml.etree
d = ET.parse("cadena.xml")
ns = {"cfdi":"http://www.sat.gob.mx/cfd/3"}
print("-------------------------")
#---------------------------
node = d.findall("//{http://www.sat.gob.mx/cfd/3}Impuestos/[@TotalImpuestosTrasladados]")[0]
for key,val in node.items():
print(key,val)
print(node.xpath("@TotalImpuestosTrasladados")[0])
#---------------------------
print("--------------------------")
node = d.findall("//cfdi:Impuestos/[@TotalImpuestosTrasladados]",ns)[0]
for key,val in node.items():
print(key,val)
print(node.xpath("@TotalImpuestosTrasladados")[0])
#---------------------------
print("----------------------------")
E = ET.XPathEvaluator(d,namespaces=ns)
print(E("//cfdi:Impuestos/@TotalImpuestosTrasladados")[0])
[CODE]
sudo perf stat -a -B -e cache-references,cache-misses,cycles,instructions,branches,branch-misses,stalled-cycles-frontend,stalled-cycles-backend,faults,migrations,L1-dcache-loads,L1-dcache-load-misses,LLC-loads,LLC-load-misses python main.py
-------------------------
363104
-------------------------
('TotalImpuestosRetenidos', '1196492')
('TotalImpuestosTrasladados', '363104')
363104
--------------------------
('TotalImpuestosRetenidos', '1196492')
('TotalImpuestosTrasladados', '363104')
363104
----------------------------
363104
Performance counter stats for 'system wide':
124 036 315 cache-references [32.68%]
1 408 213 cache-misses # 1.135 % of all cache refs [33.80%]
425 334 049 cycles [34.92%]
398 416 294 instructions # 0.94 insns per cycle
# 0.14 stalled cycles per insn [36.04%]
98 415 633 branches [35.78%]
2 824 985 branch-misses # 2.87% of all branches [34.67%]
56 174 078 stalled-cycles-frontend # 13.21% frontend cycles idle [33.55%]
56 535 015 stalled-cycles-backend # 13.29% backend cycles idle [32.43%]
2 885 faults [100.00%]
0 migrations
157 605 242 L1-dcache-loads [31.54%]
915 938 L1-dcache-load-misses # 0.58% of all L1-dcache hits [31.54%]
2 029 911 LLC-loads [31.54%]
401 918 LLC-load-misses # 19.80% of all LL-cache hits [31.54%]
0.355013604 seconds time elapsed
Voy a hacer lo mismo con el código que puse al inicio
#include <stdio.h>
volatile char temp0[20];
volatile int temp1[20];
int main(int argc, char **argv)
{
int k,i = 0;
for( k = 0; k < 10; ++k )
{
temp0[i] = k;
temp0[i+1] = k +1;
temp1[i] = k;
temp1[i+1] = k +1;
i = i +2;
}
}
Performance counter stats for 'system wide' (10000 runs):
350 010 cache-references ( +- 0.84% ) [79.77%]
15 870 cache-misses # 4.534 % of all cache refs ( +- 0.70% ) [98.15%]
2 486 998 cycles ( +- 0.86% ) [99.14%]
1 055 928 instructions # 0.42 insns per cycle
# 0.01 stalled cycles per insn ( +- 0.93% ) [99.31%]
<not counted> branches
<not counted> branch-misses
<not counted> stalled-cycles-frontend
<not counted> stalled-cycles-backend
155 faults ( +- 0.01% ) [99.98%]
0 migrations
<not counted> L1-dcache-loads
<not counted> L1-dcache-load-misses
<not counted> LLC-loads
<not counted> LLC-load-misses
0.000976747 seconds time elapsed ( +- 0.89% )
#include <stdio.h>
volatile char temp0[20];
volatile int temp1[20];
int main(int argc, char **argv)
{
int k,i = 0;
for(k=0; k < 20; ++k)
{
temp0[k] = k;
temp1[k] = k;
}
}
Performance counter stats for 'system wide' (10000 runs):
357 266 cache-references ( +- 0.83% ) [78.56%]
16 297 cache-misses # 4.562 % of all cache refs ( +- 0.72% ) [98.56%]
2 557 624 cycles ( +- 0.84% ) [99.31%]
1 096 564 instructions # 0.43 insns per cycle
# 0.01 stalled cycles per insn ( +- 0.97% ) [99.34%]
<not counted> branches
<not counted> branch-misses
<not counted> stalled-cycles-frontend
<not counted> stalled-cycles-backend
155 faults ( +- 0.01% ) [99.98%]
0 migrations
<not counted> L1-dcache-loads
<not counted> L1-dcache-load-misses
<not counted> LLC-loads
<not counted> LLC-load-misses
0.001006972 seconds time elapsed ( +- 0.88% )
Por lo general este es el comportamiento, pero no nos vayamos con la finta, ya que al final, en este caso, estamos a merced de un kernel que controla el acceso a memoria y el flujo de nuestros programas.