Programexempel från Progmet-föreläsning 13, måndag 12 oktober 2009 ================================================================== 1. Forts från förra gången: 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 Bitfält i poster ---------------- 2. 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-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) 3. En abstrakt datatyp: mängd av heltal --------------------------------------- Variant 1 - fast array av tal, ett tal per position --------------------------------------------------- /* bilnummer.c */ #include #include "IntSet.h" int main(void) { IntSet mina_bilnummer; IntSet_init(&mina_bilnummer); printf("Mata in heltalsdelen av bilnummer. Avsluta med ett ogiltigt tal.\n"); int bilnumret; while (scanf("%d", &bilnumret) == 1) { if (IntSet_is_member(&mina_bilnummer, bilnumret)) printf("Fanns redan.\n"); else { printf("Nytt!\n"); IntSet_add(&mina_bilnummer, bilnumret); } } IntSet_cleanup(&mina_bilnummer); return 0; } /* IntSet.h */ #ifndef INTSET_H #define INTSET_H #define INTSET_MAX_MEMBERS 1000 struct IntSet { int members[INTSET_MAX_MEMBERS]; int nr_members; }; typedef struct IntSet IntSet; extern void IntSet_init(IntSet* isp); extern void IntSet_add(IntSet* isp, int n); extern int IntSet_is_member(IntSet* isp, int n); extern void IntSet_remove(IntSet* isp, int n); extern void IntSet_cleanup(IntSet* isp); #endif /* IntSet.c */ #include #include #include "IntSet.h" void IntSet_init(IntSet* isp) { isp->nr_members = 0; } void IntSet_add(IntSet* isp, int new_number) { if (IntSet_is_member(isp, new_number)) { // Already a member, so do nothing } else if (isp->nr_members == INTSET_MAX_MEMBERS) { fprintf(stderr, "IntSet: Set full. Sorry.\n"); exit(EXIT_FAILURE); } else { isp->members[isp->nr_members++] = new_number; } } /* void int IntSet_is_member(IntSet* isp, int wanted) { for (int i = 0; i < isp->nr_members; ++i) if (isp->members[i] == wanted) return 1; return 0; } */ static int find_position(IntSet* isp, int wanted) { for (int i = 0; i < isp->nr_members; ++i) if (isp->members[i] == wanted) return i; return -1; } int IntSet_is_member(IntSet* isp, int wanted) { return find_position(isp, wanted) != -1; } void IntSet_remove(IntSet* isp, int doomed) { int position = find_position(isp, doomed); if (position == -1) { // Not a member, so do nothing } else { for (int i = position; i < isp->nr_members - 1; ++i) isp->members[i] = isp->members[i + 1]; --isp->nr_members; } } void IntSet_cleanup(IntSet* isp) { isp->nr_members = 0; } Variant 2 - dynamisk allokerad array av tal, ett tal per position ----------------------------------------------------------------- /* IntSet.h */ #ifndef INTSET_H #define INTSET_H struct IntSet { int* members; int allocated_members; int nr_members; }; typedef struct IntSet IntSet; extern void IntSet_init(IntSet* isp); extern void IntSet_add(IntSet* isp, int n); extern int IntSet_is_member(IntSet* isp, int n); extern void IntSet_remove(IntSet* isp, int n); extern void IntSet_cleanup(IntSet* isp); #endif /* IntSet.c */ #include #include #include "IntSet.h" void IntSet_init(IntSet* isp) { isp->members = NULL; isp->allocated_members = 0; isp->nr_members = 0; } void IntSet_add(IntSet* isp, int new_number) { if (IntSet_is_member(isp, new_number)) { // Already a member, so do nothing } else { if (isp->nr_members == isp->allocated_members) { if (isp->allocated_members == 0) isp->allocated_members = 16; else isp->allocated_members *= 2; isp->members = realloc(isp->members, isp->allocated_members * sizeof(isp->members[0])); if (isp->members == NULL) { fprintf(stderr, "IntSet: Memory full. Couldn't allocate %ld bytes. Sorry.\n", (long int)(isp->allocated_members * sizeof(isp->members[0]))); exit(EXIT_FAILURE); } } isp->members[isp->nr_members++] = new_number; } } static int find_position(IntSet* isp, int wanted) { for (int i = 0; i < isp->nr_members; ++i) if (isp->members[i] == wanted) return i; return -1; } int IntSet_is_member(IntSet* isp, int wanted) { return find_position(isp, wanted) != -1; } void IntSet_remove(IntSet* isp, int doomed) { int position = find_position(isp, doomed); if (position == -1) { // Not a member, so do nothing } else { for (int i = position; i < isp->nr_members - 1; ++i) isp->members[i] = isp->members[i + 1]; --isp->nr_members; } } void IntSet_cleanup(IntSet* isp) { free(isp->members); isp->members = NULL; isp->allocated_members = 0; isp->nr_members = 0; } Variant 3 - fast array av flaggor, en per möjligt tal ----------------------------------------------------- /* IntSet.h */ #ifndef INTSET_H #define INTSET_H #define INTSET_MAX_NUMBER 1000 struct IntSet { int members[INTSET_MAX_NUMBER + 1]; }; typedef struct IntSet IntSet; extern void IntSet_init(IntSet* isp); extern void IntSet_add(IntSet* isp, int n); extern int IntSet_is_member(IntSet* isp, int n); extern void IntSet_remove(IntSet* isp, int n); extern void IntSet_cleanup(IntSet* isp); #endif /* IntSet.c */ #include #include #include "IntSet.h" void IntSet_init(IntSet* isp) { for (int i = 0; i <= INTSET_MAX_NUMBER; ++i) isp->members[i] = 0; } void IntSet_add(IntSet* isp, int new_number) { if (IntSet_is_member(isp, new_number)) { // Already a member, so do nothing } else if (new_number < 0 || new_number > INTSET_MAX_NUMBER) { fprintf(stderr, "IntSet: Number outside allowed range. Sorry.\n"); exit(EXIT_FAILURE); } else { isp->members[new_number] = 1; } } int IntSet_is_member(IntSet* isp, int wanted) { if (wanted < 0 || wanted > INTSET_MAX_NUMBER) return 0; else return isp->members[wanted]; } void IntSet_remove(IntSet* isp, int doomed) { if (doomed < 0 || doomed > INTSET_MAX_NUMBER) { // Outside range, so can't be in the set. Do nothing. exit(EXIT_FAILURE); } else { isp->members[doomed] = 0; } } void IntSet_cleanup(IntSet* isp) { for (int i = 0; i <= INTSET_MAX_NUMBER; ++i) isp->members[i] = 0; } Variant 4 - fast array av flaggor, en per möjligt tal, men packad ----------------------------------------------------------------- /* IntSet.h */ #ifndef INTSET_H #define INTSET_H #include #define INTSET_MAX_NUMBER 1000 #define INTSET_NR_BYTES ((INTSET_MAX_NUMBER + 1) / CHAR_BIT + 1) struct IntSet { char members[INTSET_NR_BYTES]; }; typedef struct IntSet IntSet; extern void IntSet_init(IntSet* isp); extern void IntSet_add(IntSet* isp, int n); extern int IntSet_is_member(IntSet* isp, int n); extern void IntSet_remove(IntSet* isp, int n); extern void IntSet_cleanup(IntSet* isp); #endif /* IntSet.c */ #include #include #include "IntSet.h" void IntSet_init(IntSet* isp) { for (int i = 0; i < INTSET_NR_BYTES; ++i) isp->members[i] = 0; } void IntSet_add(IntSet* isp, int new_number) { if (IntSet_is_member(isp, new_number)) { // Already a member, so do nothing } else if (new_number < 0 || new_number > INTSET_MAX_NUMBER) { fprintf(stderr, "IntSet: Number outside allowed range. Sorry.\n"); exit(EXIT_FAILURE); } else { isp->members[new_number / CHAR_BIT] |= (1 << new_number % CHAR_BIT); } } int IntSet_is_member(IntSet* isp, int wanted) { if (wanted < 0 || wanted > INTSET_MAX_NUMBER) return 0; else return (isp->members[wanted / CHAR_BIT] & (1 << wanted % CHAR_BIT)) != 0; // return isp->members[wanted / CHAR_BIT] & (1 << wanted % CHAR_BIT); -- Doesn't work: } void IntSet_remove(IntSet* isp, int doomed) { if (doomed < 0 || doomed > INTSET_MAX_NUMBER) { // Outside range, so can't be in the set. Do nothing. exit(EXIT_FAILURE); } else { isp->members[doomed / CHAR_BIT] &= ~(1 << doomed % CHAR_BIT); } } void IntSet_cleanup(IntSet* isp) { for (int i = 0; i <= INTSET_NR_BYTES; ++i) isp->members[i] = 0; } Variant 5 - binärt träd ----------------------- /* IntSet.h */ #ifndef INTSET_H #define INTSET_H struct IntSetNode { int member; struct IntSetNode* left; struct IntSetNode* right; }; struct IntSet { struct IntSetNode* root; }; typedef struct IntSet IntSet; extern void IntSet_init(IntSet* isp); extern void IntSet_add(IntSet* isp, int n); extern int IntSet_is_member(IntSet* isp, int n); extern void IntSet_remove(IntSet* isp, int n); extern void IntSet_cleanup(IntSet* isp); #endif /* IntSet.c */ .... Variant 6 - hashtabell ---------------------- /* IntSet.h */ #ifndef INTSET_H #define INTSET_H #define INTSET_HASH_TABLE_SIZE 4703 struct IntSetHashNode { int member; struct IntSetHashNode* next_in_bucket; }; struct IntSet { struct IntSetHashNode* hash_table[INTSET_HASH_TABLE_SIZE]; }; typedef struct IntSet IntSet; extern void IntSet_init(IntSet* isp); extern void IntSet_add(IntSet* isp, int new_number); extern int IntSet_is_member(IntSet* isp, int wanted); extern void IntSet_remove(IntSet* isp, int wanted); extern void IntSet_cleanup(IntSet* isp); #endif /* IntSet.c */ #include #include #include "IntSet.h" void IntSet_init(IntSet* isp) { for (int i = 0; i < INTSET_HASH_TABLE_SIZE; ++i) isp->hash_table[i] = NULL; } static unsigned int hash_function(int n) { if (n < 0) n = -n; return n % INTSET_HASH_TABLE_SIZE; } void IntSet_add(IntSet* isp, int new_number) { if (IntSet_is_member(isp, new_number)) { // Already a member, so do nothing } else { struct IntSetHashNode* newnode = malloc(sizeof(struct IntSetHashNode)); if (newnode == NULL) { fprintf(stderr, "IntSet: Minnet är fullt. Vi beklagar. Adjö.\n"); exit(EXIT_FAILURE); } newnode->member = new_number; unsigned int position = hash_function(new_number); newnode->next_in_bucket = isp->hash_table[position]; isp->hash_table[position] = newnode; } } int IntSet_is_member(IntSet* isp, int wanted) { unsigned int position = hash_function(wanted); struct IntSetHashNode* p = isp->hash_table[position]; while (p != NULL) { if (p->member == wanted) return 1; else p = p->next_in_bucket; } return 0; } void IntSet_remove(IntSet* isp, int wanted) { unsigned int position = hash_function(wanted); struct IntSetHashNode* p = isp->hash_table[position]; struct IntSetHashNode* previous = NULL; while (p != NULL) { if (p->member == wanted) { struct IntSetHashNode* doomed = p; if (previous == NULL) isp->hash_table[position] = p->next_in_bucket; else previous->next_in_bucket = p->next_in_bucket; free(doomed); return; } previous = p; p = p->next_in_bucket; } } void IntSet_cleanup(IntSet* isp) { for (int i = 0; i < INTSET_HASH_TABLE_SIZE; ++i) { struct IntSetHashNode* p = isp->hash_table[i]; while (p != NULL) { struct IntSetHashNode* doomed = p; p = p->next_in_bucket; free(doomed); } } } 4. Mer hårdvarunära programmering --------------------------------- minesmappning volatile