Your cart is currently empty!
Purpose: To go over: Compiler optimizations Program profiling (timing) Header files Linking and object file layout Computing Please ssh into one of the following: 140.192.36.184 140.192.36.185 140.192.36.186 140.192.36.187 or use your own Linux machine. Please submit a .zip file (not .7z or any other non-standard compression!) file of your header file and a .txt/.pdf/.doc/.odt file…
To go over:
Compiler optimizations
Program profiling (timing)
Header files
Linking and object file layout
Please ssh into one of the following:
140.192.36.184
140.192.36.185
140.192.36.186
140.192.36.187
or use your own Linux machine.
Please submit a .zip file (not .7z or any other non-standard compression!) file of your header file and a .txt/.pdf/.doc/.odt file containing your answer to the questions.
/*-------------------------------------------------------------------------* *--- ---* *--- wordCounter.c ---* *--- ---* *--- This file defines a program that counts the words in a file ---* *--- using 2 different data-structures. ---* *--- ---* *--- ---- ---- ---- ---- ---- ---- ---- ---- ---* *--- ---* *--- Version 1.0 2018 September 9 Joseph Phillips ---* *--- ---* *-------------------------------------------------------------------------*/ #include "wordCounterHeader.h" // PURPOSE: To hold the size of the buffer to read. int textLen; // PURPOSE: To remove the '\n' character in the string pointed to by '\n', // if it exists. No return value. void removeNewline (char* cPtr ) { cPtr = strchr(cPtr,'\n'); if (cPtr != NULL) *cPtr = '\0'; } // PURPOSE: To return '1' if a word is found at address '*positionHandle', // and to place a lowercased version of the word into 'word', advance // '*positionHandle' past the word, and return '1' if such a word exists. // Returns '0' if no more words are found between the starting address of // '*positionHandle' and the ending '\n' or '\0' character. int didGetWord (char** positionHandle, char* word ) { while ( (**positionHandle != '\n') && (**positionHandle != '\n') && !isalnum(**positionHandle) ) (*positionHandle)++; if ( (**positionHandle == '\n') || (**positionHandle == '\0') ) return(0); do { *word = tolower(**positionHandle); word++; (*positionHandle)++; } while ( isalnum(**positionHandle) ); *word = '\0'; return(1); } int main (int argc, char* argv[] ) { char filename[SMALL_TEXT_LEN]; FILE* filePtr; int choice; int length = 1024; textLen = 4 * length; printf("File name to read: "); fgets(filename,SMALL_TEXT_LEN,stdin); removeNewline(filename); filePtr = fopen(filename,"r"); if (filePtr == NULL) { fprintf(stderr,"Could not open %s\n",filename); exit(EXIT_FAILURE); } do { char choiceText[SMALL_TEXT_LEN]; printf ("Which algorithm would you like to run:\n" "(1) Count words with tree\n" "(2) Count words with linked-list\n" "\n" "Your choice? " ); fgets(choiceText,SMALL_TEXT_LEN,stdin); choice = atoi(choiceText); } while ( (choice < 1) || (choice > 2) ); printf("\n\n"); switch (choice) { case 1 : { struct TreeNode* rootPtr = buildTree(filePtr); printTree(rootPtr); freeTree (rootPtr); } break; case 2 : { struct ListNode* firstPtr= buildList(filePtr); printList(firstPtr); freeList (firstPtr); } break; } fclose(filePtr); return(EXIT_SUCCESS); }
/*-------------------------------------------------------------------------* *--- ---* *--- tree.c ---* *--- ---* *--- This file defines functions that build, print and free a ---* *--- tree of struct TreeNode instances for the wordCounter program. ---* *--- ---* *--- ---- ---- ---- ---- ---- ---- ---- ---- ---* *--- ---* *--- Version 1.0 2018 September 9 Joseph Phillips ---* *--- ---* *-------------------------------------------------------------------------*/ #include "wordCounterHeader.h" // PURPOSE: To build and return a tree of struct TreeNode instances telling // the counts of the words found in file '*filePtr'. struct TreeNode* buildTree (FILE* filePtr ) { struct TreeNode* rootPtr = NULL; struct TreeNode* listPrev; struct TreeNode* listRun; struct TreeNode* newPtr; int compResult; char* line = (char*)malloc(textLen); char word[SMALL_TEXT_LEN]; while ( fgets(line,textLen,filePtr) != NULL ) { char* lineRun = line; while ( didGetWord(&lineRun,word) ) { listPrev = NULL; for (listRun = rootPtr; listRun != NULL; ) { if ( (compResult = strcmp(listRun->wordCPtr_,word)) == 0) break; listPrev = listRun; if (compResult > 0) listRun = listRun->leftPtr_; else listRun = listRun->rightPtr_; } if (listRun == NULL) { newPtr = (struct TreeNode*)malloc(sizeof(struct TreeNode)); newPtr->wordCPtr_ = strdup(word); newPtr->count_ = 1; newPtr->leftPtr_ = NULL; newPtr->rightPtr_ = NULL; if (rootPtr == NULL) rootPtr = newPtr; else if (compResult > 0) listPrev->leftPtr_ = newPtr; else listPrev->rightPtr_ = newPtr; } else (listRun->count_)++; } } free(line); return(rootPtr); } // PURPOSE: To print the subtree rooted at '*nodePtr'. No return value. void printTree (struct TreeNode* nodePtr ) { if (nodePtr == NULL) return; printTree(nodePtr->leftPtr_); printf("%s\t%d\n",nodePtr->wordCPtr_,nodePtr->count_); printTree(nodePtr->rightPtr_); } // PURPOSE: To free the subtree rooted at '*nodePtr'. No return value. void freeTree (struct TreeNode* nodePtr ) { if (nodePtr == NULL) return; freeTree(nodePtr->leftPtr_); freeTree(nodePtr->rightPtr_); free(nodePtr->wordCPtr_); free(nodePtr); }
/*-------------------------------------------------------------------------* *--- ---* *--- list.c ---* *--- ---* *--- This file defines functions that build, print and free a ---* *--- list of struct ListNode instances for the wordCounter program. ---* *--- ---* *--- ---- ---- ---- ---- ---- ---- ---- ---- ---* *--- ---* *--- Version 1.0 2018 September 9 Joseph Phillips ---* *--- ---* *-------------------------------------------------------------------------*/ #include "wordCounterHeader.h" // PURPOSE: To build and return a list of struct ListNode instances telling // the counts of the words found in file '*filePtr'. struct ListNode* buildList (FILE* filePtr ) { struct ListNode* firstPtr = NULL; struct ListNode* lastPtr = NULL; struct ListNode* listRun; struct ListNode* newPtr; char* line = (char*)malloc(textLen); char word[SMALL_TEXT_LEN]; while ( fgets(line,textLen,filePtr) != NULL ) { char* lineRun = line; while ( didGetWord(&lineRun,word) ) { for (listRun = firstPtr; listRun != NULL; listRun = listRun->nextPtr_) if (strcmp(listRun->wordCPtr_,word) == 0) break; if (listRun == NULL) { newPtr = (struct ListNode*)malloc(sizeof(struct ListNode)); newPtr->wordCPtr_ = strdup(word); newPtr->count_ = 1; newPtr->nextPtr_ = NULL; if (firstPtr == NULL) firstPtr = newPtr; else lastPtr->nextPtr_ = newPtr; lastPtr = newPtr; } else (listRun->count_)++; } } free(line); return(firstPtr); } // PURPOSE: To print the list pointed to by '*firstPtr'. No return value. void printList (struct ListNode* firstPtr ) { struct ListNode* listRun; for (listRun = firstPtr; listRun != NULL; listRun = listRun->nextPtr_) printf("%s\t%d\n",listRun->wordCPtr_,listRun->count_); } // PURPOSE: To free the list pointed to by '*firstPtr'. No return value. void freeList (struct ListNode* firstPtr ) { struct ListNode* listRun; struct ListNode* nextPtr; for (listRun = firstPtr; listRun != NULL; listRun = nextPtr) { nextPtr = listRun->nextPtr_; free(listRun->wordCPtr_); free(listRun); } }
Hey! Ain’t something missing!?!
Yeah, that is right. There is no wordCounterHeader.h
.
Please write one so that you can compile the program! Please be sure to declare only what is needed in common.
Please add to this incomplete one:
/*-------------------------------------------------------------------------* *--- ---* *--- wordCounterHeader.h ---* *--- ---* *--- This file includes common header files and declares structs ---* *--- needed by .c files of the wordCounter program. ---* *--- ---* *--- ---- ---- ---- ---- ---- ---- ---- ---- ---* *--- ---* *--- Version 1.0 2018 September 9 Joseph Phillips ---* *--- ---* *-------------------------------------------------------------------------*/ //--- Common inclusions: ---// #include <stdlib.h> #include <stdio.h> #include <string.h> //--- Common constants: ---// #define SMALL_TEXT_LEN 256 //--- Common types: ---// struct TreeNode { char* wordCPtr_; int count_; struct TreeNode* leftPtr_; struct TreeNode* rightPtr_; }; struct ListNode { char* wordCPtr_; int count_; struct ListNode* nextPtr_; }; //--- Declarations of global functions: ---// // YOUR CODE HERE!
Compile and run the program without any extra optimizations, but with profiling for timing:
gcc -c -pg -O0 wordCounter.c gcc -c -pg -O0 tree.c gcc -c -pg -O0 list.c gcc wordCounter.o tree.o list.o -pg -O0 -o wordCounterO0
Run the program twice timing it both times, and answer the following:
$ ./wordCounterO0
File name to read: originOfSpecies.txt Which algorithm would you like to run: (1) Count words with tree (2) Count words with linked-list Your choice? 1
buildTree() self seconds |
_____________ |
$ ./wordCounterO0
File name to read: originOfSpecies.txt Which algorithm would you like to run: (1) Count words with tree (2) Count words with linked-list Your choice? 2
buildList() self seconds |
_____________ |
Compile and run the program with optimization, but with profiling for timing:
gcc -c -pg -O2 wordCounter.c gcc -c -pg -O2 tree.c gcc -c -pg -O2 list.c gcc wordCounter.o tree.o list.o -pg -O2 -o wordCounterO2
Run the program twice timing it both times, and answer the following:
$ ./wordCounterO2
File name to read: originOfSpecies.txt Which algorithm would you like to run: (1) Count words with tree (2) Count words with linked-list Your choice? 1
buildTree() self seconds |
_____________ |
$ ./wordCounterO2
File name to read: originOfSpecies.txt Which algorithm would you like to run: (1) Count words with tree (2) Count words with linked-list Your choice? 2
buildList() self seconds |
_____________ |
Please find the following inside of wordCounterO0
by using objdump
to show it (if it exists in the executable) or by using objdump
to disassemble the code and showing where the code manipulates the heap or stack.
Show a disassembly or objdump. You do not have to show all of the objdump result if it is too long, but (1) please show the relevant output, and (2) please show the objdump
command that you used to generate it.
The string "File
in
name to read: "main()
The local variable rootPtr
in buildTree()
The code for printList()
The global variable textLen
Question |
Command |
Result |
---|---|---|
(A) |
______________________ |
________________________________ |
(B) |
______________________ |
________________________________ |
(C) |
______________________ |
________________________________ |
(D) |
______________________ |
________________________________ |
Find and show at least 2 examples (total) of the following optimizations in either wordCounterO0
or wordCounterO2
.
usage of registers to hold vars (as opposed to the stack)
code motion
reduction in strength
For both:
Tell if it exists in either wordCounterO0
, wordCounterO2
, or both, and
Show these optimizations in the disassembly of the function that has it