a@ubuntu:~/Desktop$ valgrind --tool=cachegrind ./skrzaty64.out < skr5l.in ==11809== Cachegrind, a cache and branch-prediction profiler ==11809== Copyright (C) 2002-2012, and GNU GPL'd, by Nicholas Nethercote et al. ==11809== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info ==11809== Command: ./skrzaty64.out ==11809== --11809-- warning: L3 cache found, using its data for the LL simulation. 638002 ==11809== ==11809== I refs: 10,654,292,679 ==11809== I1 misses: 1,111 ==11809== LLi misses: 1,089 ==11809== I1 miss rate: 0.00% ==11809== LLi miss rate: 0.00% ==11809== ==11809== D refs: 5,464,443,220 (4,650,042,835 rd + 814,400,385 wr) ==11809== D1 misses: 7,638,302 ( 6,350,038 rd + 1,288,264 wr) ==11809== LLd misses: 5,330 ( 4,703 rd + 627 wr) ==11809== D1 miss rate: 0.1% ( 0.1% + 0.1% ) ==11809== LLd miss rate: 0.0% ( 0.0% + 0.0% ) ==11809== ==11809== LL refs: 7,639,413 ( 6,351,149 rd + 1,288,264 wr) ==11809== LL misses: 6,419 ( 5,792 rd + 627 wr) ==11809== LL miss rate: 0.0% ( 0.0% + 0.0% ) a@ubuntu:~/Desktop$ cg_annotate cachegrind.out.11809 /home/a/Desktop/skrzaty64.cpp -------------------------------------------------------------------------------- I1 cache: 32768 B, 64 B, 8-way associative D1 cache: 32768 B, 64 B, 8-way associative LL cache: 6291456 B, 64 B, 12-way associative Command: ./skrzaty64.out Data file: cachegrind.out.11809 Events recorded: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw Events shown: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw Event sort order: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw Thresholds: 0.1 100 100 100 100 100 100 100 100 Include dirs: User annotated: /home/a/Desktop/skrzaty64.cpp Auto-annotation: off -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw -------------------------------------------------------------------------------- 10,654,292,679 1,111 1,089 4,650,042,835 6,350,038 4,703 814,400,385 1,288,264 627 PROGRAM TOTALS -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw file:function -------------------------------------------------------------------------------- 8,088,634,294 13 13 4,007,058,498 4,856,593 0 10,995,685 390 389 /home/a/Desktop/skrzaty64.cpp:main 1,250,348,057 52 52 415,553,275 161,742 73 213,763,190 638,004 0 /build/buildd/eglibc-2.17/stdio-common/vfscanf.c:_IO_vfscanf 712,649,351 7 7 5,742,027 638,004 1 502,108,361 0 0 /build/buildd/eglibc-2.17/string/../sysdeps/i386/i686/multiarch/memset-sse2.S:__memset_sse2 391,929,537 11 11 119,405,711 20,633 2 37,386,390 10,306 0 /build/buildd/eglibc-2.17/stdlib/strtol_l.c:____strtol_l_internal 84,742,484 2 2 39,878,816 0 0 9,969,704 0 0 /build/buildd/eglibc-2.17/libio/genops.c:_IO_sputbackc 49,848,520 2 2 22,431,834 0 0 19,939,408 0 0 /build/buildd/eglibc-2.17/stdlib/strtol.c:__strtol_internal 39,878,816 2 2 12,462,130 21,995 0 17,446,982 638,002 0 /build/buildd/eglibc-2.17/stdio-common/scanf.c:scanf 23,778,280 1 1 23,778,280 0 0 0 0 0 /build/buildd/eglibc-2.17/string/../sysdeps/i386/i686/multiarch/strcat.S:??? -------------------------------------------------------------------------------- -- User-annotated source: /home/a/Desktop/skrzaty64.cpp -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw -- line 6 ---------------------------------------- . . . . . . . . . #include . . . . . . . . . #include . . . . . . . . . #include . . . . . . . . . . . . . . . . . . using namespace std; . . . . . . . . . . . . . . . . . . static inline void setFalse(uint64_t *a, int pos) . . . . . . . . . { 44,506,104 1 1 3,708,842 0 0 0 0 0 a[pos / 64] &= ~((uint64_t) 1 << (pos % 64)); . . . . . . . . . } . . . . . . . . . static inline int getState(uint64_t *a, int pos) . . . . . . . . . { 20,416,096 2 2 4,466,021 0 0 2,552,012 0 0 return (a[pos / 64] & (uint64_t)1 << (pos % 64)) >> pos % 64; . . . . . . . . . } . . . . . . . . . static inline void setTrue(uint64_t *a, int pos) . . . . . . . . . { . . . . . . . . . a[pos / 64] |= (uint64_t) 1 << (pos % 64); . . . . . . . . . } . . . . . . . . . 2,552,013 1 1 319,001 0 0 638,003 0 0 int main(void) 7 1 1 0 0 0 4 0 0 { . . . . . . . . . int iloscSkrzatow, czasDoSnu; 4 0 0 0 0 0 3 0 0 scanf("%i", &iloscSkrzatow); 4 1 1 0 0 0 3 0 0 scanf("%i", &czasDoSnu); 7,830 1 1 2 0 0 3,129 195 194 uint64_t *safe = new uint64_t[iloscSkrzatow / 64 + 1](); 3,135 1 1 2 0 0 0 0 0 for (int a = 0; a < iloscSkrzatow / 64 + 1; a++) 4,689 0 0 0 0 0 3,126 0 0 safe[a] = 0; 3 0 0 1 0 0 2 0 0 safe[0] = 1; 7,823 1 1 0 0 0 3,128 195 195 uint64_t *safeT = new uint64_t[iloscSkrzatow / 64 + 1](); 2,552,014 0 0 1,914,008 0 0 1 0 0 for (int i = 0; i < czasDoSnu; i++) . . . . . . . . . { 2,552,012 0 0 0 0 0 0 0 0 memset(safeT,255,iloscSkrzatow / 8); 6,380,030 1 1 638,003 0 0 0 0 0 for(int m = 0; m < iloscSkrzatow % 8; m++) . . . . . . . . . setTrue(safeT,iloscSkrzatow - iloscSkrzatow % 8 + m); . . . . . . . . . int length; 2,552,012 1 1 0 0 0 1,914,009 0 0 scanf("%i", &length); 9,391,281 0 0 2,492,424 0 0 0 0 0 for (int j = 0; j < length; j++) . . . . . . . . . { . . . . . . . . . int temp; 7,417,684 1 1 0 0 0 5,563,263 0 0 scanf("%i", &temp); 1,854,421 0 0 1,854,421 0 0 0 0 0 setFalse(safeT, temp - 1); . . . . . . . . . } 1,500,585,401 0 0 957,005 0 0 0 0 0 for (int m = 0; m < iloscSkrzatow / 64 + 1; m++) . . . . . . . . . { 2,995,428,773 1 1 1,996,314,511 2,734,773 0 319,002 0 0 if (safe[m] & safeT[m]) . . . . . . . . . { 1,496,114,690 0 0 0 0 0 0 0 0 for (int p = 0; p < iloscSkrzatow / 64 + 1; p++) 1,994,394,252 0 0 1,994,394,252 2,121,820 0 0 0 0 safe[p] |= safeT[p]; . . . . . . . . . break; . . . . . . . . . } . . . . . . . . . } 1,914,009 0 0 0 0 0 0 0 0 if (getState(safe, iloscSkrzatow - 1)) . . . . . . . . . { . . . . . . . . . printf("%i\n", i); . . . . . . . . . //system("pause"); //DEBUG . . . . . . . . . return 0; . . . . . . . . . } . . . . . . . . . //delete[] safeT; . . . . . . . . . } . . . . . . . . . printf("%i\n", czasDoSnu); . . . . . . . . . //system("pause"); //DEBUG 7 0 0 5 0 0 0 0 0 } . . . . . . . . . -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw -------------------------------------------------------------------------------- 76 1 1 86 76 0 1 0 62 percentage of events annotated