Programexempel från Progmet-föreläsning 10, torsdag 29 september 2011 ===================================================================== Dagens program (preliminärt): 1. Fortsättning på hashtabeller (kallas "söktabeller" i kompendiet): hashwordcounter 2. Läs mer om binära träd och hashtabeller 3. Lågnivåprogrammering: bitar och bytes 4. Mer om hårdvarunära programmering 5. Trådar 1. hashwordcounter.c ==================== #include #include #include #define MAX_WORD_LENGTH 20 #define HASH_TABLE_SIZE 47 struct HashNode { char key[MAX_WORD_LENGTH + 1]; int count; struct HashNode* next_in_bucket; }; unsigned int hashfunktion(unsigned char *s) { unsigned int resultat = 5381; int c; while ((c = *s++) != '\0') resultat = resultat * 33 + c; return resultat % HASH_TABLE_SIZE; } unsigned int samma_hashfunktion(unsigned char *s) { unsigned int resultat = 5381; int n = strlen(s); for (int i = 0; i < n; ++i) resultat = resultat * 33 + s[i]; return resultat % HASH_TABLE_SIZE; } void hash_insert(struct HashNode* ht[], char* newkey) { int position = hashfunktion(newkey); struct HashNode* p = ht[position]; while (p != NULL) { if (strcmp(newkey, p->key) == 0) { ++p->count; return; } p = p->next_in_bucket; } struct HashNode* newnode = malloc(sizeof(struct HashNode)); strcpy(newnode->key, newkey); newnode->count = 1; newnode->next_in_bucket = ht[position]; ht[position] = newnode; } void print_table(struct HashNode* ht[]) { for (int position = 0; position < HASH_TABLE_SIZE; ++position) { struct HashNode* p = ht[position]; while (p != NULL) { printf("%s: %d\n", p->key, p->count); p = p->next_in_bucket; } } } int main(void) { struct HashNode* hashtabellen[HASH_TABLE_SIZE]; for (int i = 0; i < HASH_TABLE_SIZE; ++i) hashtabellen[i] = NULL; char key[MAX_WORD_LENGTH + 1]; while (scanf("%20s", key) == 1) hash_insert(hashtabellen, key); print_table(hashtabellen); return 0; } 2. Läs mer om binära träd och hashtabeller ========================================== Om Programkonstruktion: Gunnar Jokis kompendium (på kursens hemsida) kapitel 4 "Vi lär oss det där med data: Grunder om lagringsstrukturer" (på hemsidan) Gunnar Jokis kompendium (på kursens hemsida): avsnitt 5.1 om träd avsnitt 5.2 om hashtabeller Bilting, "Vägen till C", 2000: rekursion beskrivs på sid 135-136 och används på sid 213 binärsökning nämns på sid 247 avsnitt 8.2.2 om hashtabeller avsnitt 8.2.3 om binära träd Janlert et al, "Datatyper och algoritmer", 2000: kapitel 11 om binära träd kapitel 14 om binära sökträd avsnitt 15.3 om hashtabeller Weiss, "Data Structures and Algorithm Analysis in C++", 3d Ed, 2006: binärsökning i avsnitt 2.4.4 (sid 58-60) binära sökträd i kapitel 4 hashtabeller i kapitel 5 3. Lågnivåprogrammering: bitar och bytes ======================================== Bitar och byte (char) binärt, decimalt och hexadecimalt little-endian och big-endian Kom ihåg de bitvisa operatorerna -------------------------------- Vänsterskift: << Högerskift: >> Bitvis OCH ("AND"): & Bitvis ELLER ("OR"): | Bitvis XOR: ^ Bitvis INTE ("NOT"): ~ Jämför med logisk, inte bitvis, OCH: && Jämför med logisk, inte bitvis, ELLER: || Jämför med logisk, inte bitvis, INTE: ! Några bra operationer --------------------- Notera att & och | har konstig prioritet Är bit N satt? c & (1 << N) Sätt bit N c = c | (1 << N) c |= (1 << N) Nolla bit N c = c & ~(1 << N) c &= ~(1 << N) Toggla bit N c = c ^ (1 << N) c ^= (1 << N) Utmatning av bitarna i minnet ----------------------------- Decimalt: %d, %u Hexadecimalt: %x Binärt storlekar.c ----------- #include #include int main(void) { printf("En char är %d bitar.\n", CHAR_BIT); printf("En int är %d bitar.\n", (int)(sizeof(int) * CHAR_BIT)); printf("En long int är %d bitar.\n", (int)(sizeof(long int) * CHAR_BIT)); printf("En void-pekare är %d bitar.\n", (int)(sizeof(void*) * CHAR_BIT)); return 0; } Utmatning på en i7 med Linux (64-bitars) ---------------------------------------- En char är 8 bitar. En int är 32 bitar. En long int är 64 bitar. En void-pekare är 64 bitar. Utmatning på en Sun Sparc (32-bitars) ------------------------------------- En char är 8 bitar. En int är 32 bitar. En long int är 32 bitar. En void-pekare är 32 bitar. byte-order.c ------------ #include #include void print_int(int n) { printf("%d = %08x =", n, n); unsigned char *p = (unsigned char*)&n; for (int i = 0; i < sizeof(n); ++i) printf(" %2.2x", p[i]); printf(" = "); for (int i = 0; i < sizeof(n); ++i) { for (int b = 0; b < CHAR_BIT; ++b) printf("%d", (p[i] & 1 << (CHAR_BIT - b - 1)) >> (CHAR_BIT - b - 1)); printf(" "); } printf("\n"); } int main(void) { int i1 = -1; // 11111111 11111111 11111111 11111111 int i2 = 17; // 00000000 00000000 00000000 00010001 int i3 = 300; // 00000000 00000000 00000001 00101100 print_int(i1); print_int(i2); print_int(i3); return 0; } Utmatning på en Sun Sparc (big-endian) -------------------------------------- -1 = ffffffff = ff ff ff ff = 11111111 11111111 11111111 11111111 17 = 00000011 = 00 00 00 11 = 00000000 00000000 00000000 00010001 300 = 0000012c = 00 00 01 2c = 00000000 00000000 00000001 00101100 Utmatning på en i7 med Linux (little-endian) -------------------------------------------- -1 = ffffffff = ff ff ff ff = 11111111 11111111 11111111 11111111 17 = 00000011 = 11 00 00 00 = 00010001 00000000 00000000 00000000 300 = 0000012c = 2c 01 00 00 = 00101100 00000001 00000000 00000000 Julgranar som bitar och som bitfält: julgranar.c ------------------------------------------------ #include #include struct julgran { unsigned int ljus1 : 1; unsigned int ljus2 : 1; unsigned int ljus3 : 1; unsigned int ljus4 : 1; unsigned int ljus5 : 1; unsigned int ljus6 : 1; unsigned int ljus7 : 1; unsigned int ljus8 : 1; }; void visa_julgran_int(int julgran) { if (julgran & 1) printf("*"); else printf("-"); if (julgran & 1 << 1) printf("*"); else printf("-"); if (julgran & 1 << 2) printf("*"); else printf("-"); if (julgran & 1 << 3) printf("*"); else printf("-"); if (julgran & 1 << 4) printf("*"); else printf("-"); if (julgran & 1 << 5) printf("*"); else printf("-"); if (julgran & 1 << 6) printf("*"); else printf("-"); if (julgran & 1 << 7) printf("*"); else printf("-"); printf("\n"); } void visa_julgran_bitfalt(struct julgran julgran) { if (julgran.ljus1) printf("*"); else printf("-"); if (julgran.ljus2) printf("*"); else printf("-"); if (julgran.ljus3) printf("*"); else printf("-"); if (julgran.ljus4) printf("*"); else printf("-"); if (julgran.ljus5) printf("*"); else printf("-"); if (julgran.ljus6) printf("*"); else printf("-"); if (julgran.ljus7) printf("*"); else printf("-"); if (julgran.ljus8) printf("*"); else printf("-"); printf("\n"); } int main(void) { int julgran1; struct julgran julgran2; julgran1 = 0; julgran2.ljus1 = 0; julgran2.ljus2 = 0; julgran2.ljus3 = 0; julgran2.ljus4 = 0; julgran2.ljus5 = 0; julgran2.ljus6 = 0; julgran2.ljus7 = 0; julgran2.ljus8 = 0; visa_julgran_int(julgran1); visa_julgran_bitfalt(julgran2); julgran1 |= 1; julgran1 |= 1 << 1; julgran1 |= 1 << 7; julgran2.ljus1 = 1; julgran2.ljus2 = 1; julgran2.ljus8 = 1; visa_julgran_int(julgran1); visa_julgran_bitfalt(julgran2); return 0; } Utmatning --------- -------- -------- **-----* **-----* 4. Mer om hårdvarunära programmering ==================================== minesmappning (till exempel I/O-portar) volatile mappa in fil (Unix; går det i Windows?) 5. Trådar ========= simple-thread-test.c -------------------- #include #include #include static void *thread_body(void *argument) { int thread_number = (int)argument; for (int i = 0; i < 100; i++) { printf("This is thread number %d\n", thread_number); } return NULL; } int main(void) { pthread_t threads[3]; printf("Starting thread 1...\n"); pthread_create(&threads[0], NULL, thread_body, (void*)1); printf("Starting thread 2...\n"); pthread_create(&threads[1], NULL, thread_body, (void*)2); printf("Starting thread 3...\n"); pthread_create(&threads[2], NULL, thread_body, (void*)3); printf("The 3 threads are running.\n"); printf("Waiting for thread 1 to finish...\n"); pthread_join(threads[0], NULL); printf("Thread 1 finished.\n"); printf("Waiting for thread 2 to finish...\n"); pthread_join(threads[1], NULL); printf("Thread 2 finished.\n"); printf("Waiting for thread 3 to finish...\n"); pthread_join(threads[2], NULL); printf("Thread 3 finished.\n"); return EXIT_SUCCESS; } simple-thread-test.output ------------------------- Starting thread 1... Starting thread 2... Starting thread 3... This is thread number 1 This is thread number 1 This is thread number 1 This is thread number 1 This is thread number 1 This is thread number 1 This is thread number 1 This is thread number 1 This is thread number 1 This is thread number 1 This is thread number 1 This is thread number 1 This is thread number 2 The 3 threads are running. This is thread number 2 This is thread number 1 This is thread number 3 Waiting for thread 1 to finish... This is thread number 1 This is thread number 1 This is thread number 1 This is thread number 1 This is thread number 1 This is thread number 1 [...] threadcount.c ------------- #include #include #include #include #define INCREMENT 1.1 static void *thread_body(void *arg) { double* resultp = (double*)arg; double result = 0; for (int i = 0; i < 100*1000*1000; i++) { result += INCREMENT; } *resultp = result; return NULL; } int try_N_threads(int N) { pthread_t threads[N]; double results[N]; printf("Starting %d thread(s)...\n", N); struct timeval before; gettimeofday(&before, NULL); for (int i = 0; i < N; ++i) { if (pthread_create(&threads[i], NULL, thread_body, (void*)&results[i]) != 0) { printf("Couldn't create thread %d.\n", i); exit(EXIT_FAILURE); } } printf("The %d thread(s) are running.\n", N); printf("Waiting for the %d thread(s) to finish...\n", N); for (int i = 0; i < N; ++i) { if (pthread_join(threads[i], NULL) != 0) { printf("Couldn't join thread %d.\n", i); exit(EXIT_FAILURE); } // printf("results[%d] = %f\n", i, results[i]); } struct timeval after; gettimeofday(&after, NULL); double elapsed_milliseconds = (after.tv_sec - before.tv_sec) * 1e6 + (after.tv_usec - before.tv_usec); double seconds = elapsed_milliseconds / 1e6; /* printf("Elapsed: (%ld s + %ld us) = %f s\n", (long int)(after.tv_sec - before.tv_sec), (long int)(after.tv_usec - before.tv_usec), seconds); */ printf("Elapsed: %.2f s\n", seconds); double result_sum = 0; for (int i = 0; i < N; ++i) result_sum += results[i]; double operations = result_sum / INCREMENT; double mflops = operations / seconds / 1e6; printf("%d thread(s): %.2f Mflops (%.2f per thread)\n", N, mflops, mflops / N); return EXIT_SUCCESS; } int main(void) { for (int i = 1; i <= 10; ++i) try_N_threads(i); return EXIT_SUCCESS; } threadcount.output-athlon (en kärna, ingen hypertrådning) --------------------------------------------------------- Starting 1 thread(s)... The 1 thread(s) are running. Waiting for the 1 thread(s) to finish... Elapsed: 0.22 s 1 thread(s): 454.04 Mflops (454.04 per thread) Starting 2 thread(s)... The 2 thread(s) are running. Waiting for the 2 thread(s) to finish... Elapsed: 0.44 s 2 thread(s): 455.62 Mflops (227.81 per thread) Starting 3 thread(s)... The 3 thread(s) are running. Waiting for the 3 thread(s) to finish... Elapsed: 0.66 s 3 thread(s): 455.63 Mflops (151.88 per thread) Starting 4 thread(s)... The 4 thread(s) are running. Waiting for the 4 thread(s) to finish... Elapsed: 0.88 s 4 thread(s): 455.58 Mflops (113.89 per thread) [...] threadcount.output-atom (en kärna, hypertrådad) ----------------------------------------------- Starting 1 thread(s)... The 1 thread(s) are running. Waiting for the 1 thread(s) to finish... Elapsed: 0.33 s 1 thread(s): 298.98 Mflops (298.98 per thread) Starting 2 thread(s)... The 2 thread(s) are running. Waiting for the 2 thread(s) to finish... Elapsed: 0.38 s 2 thread(s): 528.71 Mflops (264.36 per thread) Starting 3 thread(s)... The 3 thread(s) are running. Waiting for the 3 thread(s) to finish... Elapsed: 0.58 s 3 thread(s): 519.68 Mflops (173.23 per thread) Starting 4 thread(s)... The 4 thread(s) are running. Waiting for the 4 thread(s) to finish... Elapsed: 0.77 s 4 thread(s): 519.20 Mflops (129.80 per thread) [...] threadcount.output-neo (två kärnor) ----------------------------------- Starting 1 thread(s)... The 1 thread(s) are running. Waiting for the 1 thread(s) to finish... Elapsed: 0.32 s 1 thread(s): 308.89 Mflops (308.89 per thread) Starting 2 thread(s)... The 2 thread(s) are running. Waiting for the 2 thread(s) to finish... Elapsed: 0.26 s 2 thread(s): 777.82 Mflops (388.91 per thread) Starting 3 thread(s)... The 3 thread(s) are running. Waiting for the 3 thread(s) to finish... Elapsed: 0.39 s 3 thread(s): 767.31 Mflops (255.77 per thread) Starting 4 thread(s)... The 4 thread(s) are running. Waiting for the 4 thread(s) to finish... Elapsed: 0.52 s 4 thread(s): 772.53 Mflops (193.13 per thread) [...] threadcount.output-i7 (fyra kärnor, hypertrådade) ------------------------------------------------- Starting 1 thread(s)... The 1 thread(s) are running. Waiting for the 1 thread(s) to finish... Elapsed: 0.13 s 1 thread(s): 745.13 Mflops (745.13 per thread) Starting 2 thread(s)... The 2 thread(s) are running. Waiting for the 2 thread(s) to finish... Elapsed: 0.11 s 2 thread(s): 1864.07 Mflops (932.04 per thread) Starting 3 thread(s)... The 3 thread(s) are running. Waiting for the 3 thread(s) to finish... Elapsed: 0.12 s 3 thread(s): 2443.91 Mflops (814.64 per thread) Starting 4 thread(s)... The 4 thread(s) are running. Waiting for the 4 thread(s) to finish... Elapsed: 0.11 s 4 thread(s): 3537.48 Mflops (884.37 per thread) Starting 5 thread(s)... The 5 thread(s) are running. Waiting for the 5 thread(s) to finish... Elapsed: 0.14 s 5 thread(s): 3568.98 Mflops (713.80 per thread) Starting 6 thread(s)... The 6 thread(s) are running. Waiting for the 6 thread(s) to finish... Elapsed: 0.16 s 6 thread(s): 3800.62 Mflops (633.44 per thread) Starting 7 thread(s)... The 7 thread(s) are running. Waiting for the 7 thread(s) to finish... Elapsed: 0.22 s 7 thread(s): 3223.82 Mflops (460.55 per thread) Starting 8 thread(s)... The 8 thread(s) are running. Waiting for the 8 thread(s) to finish... Elapsed: 0.24 s 8 thread(s): 3357.13 Mflops (419.64 per thread) Starting 9 thread(s)... The 9 thread(s) are running. Waiting for the 9 thread(s) to finish... Elapsed: 0.26 s 9 thread(s): 3476.21 Mflops (386.25 per thread) Starting 10 thread(s)... The 10 thread(s) are running. Waiting for the 10 thread(s) to finish... Elapsed: 0.26 s 10 thread(s): 3876.33 Mflops (387.63 per thread) bad-concurrency.c ----------------- // bad-concurrency.c #include #include #include int g = 0; static void *thread_body(void *argument) { int thread_number = (int)argument; for (int i = 0; i < 1000000; i++) { ++g; } return NULL; } int main(void) { pthread_t threads[3]; printf("Before: g = %d\n", g); printf("Starting thread 1...\n"); pthread_create(&threads[0], NULL, thread_body, (void*)1); printf("Starting thread 2...\n"); pthread_create(&threads[1], NULL, thread_body, (void*)2); printf("Starting thread 3...\n"); pthread_create(&threads[2], NULL, thread_body, (void*)3); printf("The 3 threads are running.\n"); printf("Waiting for thread 1 to finish...\n"); pthread_join(threads[0], NULL); printf("Thread 1 finished.\n"); printf("Waiting for thread 2 to finish...\n"); pthread_join(threads[1], NULL); printf("Thread 2 finished.\n"); printf("Waiting for thread 3 to finish...\n"); pthread_join(threads[2], NULL); printf("Thread 3 finished.\n"); printf("g = %d\n", g); return EXIT_SUCCESS; } Körexempel för bad-concurrency ------------------------------ Before: g = 0 Starting thread 1... Starting thread 2... Starting thread 3... The 3 threads are running. Waiting for thread 1 to finish... Thread 1 finished. Waiting for thread 2 to finish... Thread 2 finished. Waiting for thread 3 to finish... Thread 3 finished. g = 1109809 Ett körexempel till för bad-concurrency --------------------------------------- Before: g = 0 Starting thread 1... Starting thread 2... Starting thread 3... The 3 threads are running. Waiting for thread 1 to finish... Thread 1 finished. Waiting for thread 2 to finish... Thread 2 finished. Waiting for thread 3 to finish... Thread 3 finished. g = 1083458 good-concurrency.c ------------------ // good-concurrency.c #include #include #include int g = 0; pthread_mutex_t mutex; static void *thread_body(void *argument) { int thread_number = (int)argument; for (int i = 0; i < 1000000; i++) { pthread_mutex_lock(&mutex); ++g; pthread_mutex_unlock(&mutex); } return NULL; } int main(void) { pthread_t threads[3]; pthread_mutex_init(&mutex, 0); printf("Before: g = %d\n", g); printf("Starting thread 1...\n"); pthread_create(&threads[0], NULL, thread_body, (void*)1); printf("Starting thread 2...\n"); pthread_create(&threads[1], NULL, thread_body, (void*)2); printf("Starting thread 3...\n"); pthread_create(&threads[2], NULL, thread_body, (void*)3); printf("The 3 threads are running.\n"); printf("Waiting for thread 1 to finish...\n"); pthread_join(threads[0], NULL); printf("Thread 1 finished.\n"); printf("Waiting for thread 2 to finish...\n"); pthread_join(threads[1], NULL); printf("Thread 2 finished.\n"); printf("Waiting for thread 3 to finish...\n"); pthread_join(threads[2], NULL); printf("Thread 3 finished.\n"); printf("g = %d\n", g); pthread_mutex_destroy(&mutex); return EXIT_SUCCESS; }