Question? Leave a message!




Managing Memory (and low level Data Structures)

Managing Memory (and low level Data Structures)
Managing Memory (and low level Data Structures)Programming Principle of the Day • Avoid Premature Optimization  Don‟t even think about optimization unless your code is working, but slower than you want. Only then should you start thinking about optimizing, and then only with the aid of empirical data.  "We should forget about small efficiencies, say about 97 of the time: premature optimization is the root of all evil" Donald Knuth. http://en.wikipedia.org/wiki/Programoptimization 2 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Low Level Data Structures • We were using the standard library data structures – containers  How are these built  Low level language facilities and data structures  Closer to computer hardware (in semantics and abstraction level)  Why do we need to know how are these built  Useful techniques, applicable in other contexts  More dangerous, require solid understanding  Sometimes absolute performance matters 3 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Pointers and Arrays • Array is a kind of container, however it‟s less powerful and more dangerous • Pointers are kind of random access iterators for accessing elements of arrays • Pointers and Arrays are the most primitive data structures available in C/C++  Closely connected concepts, inseparable in real world usage 4 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Pointers • A pointer is a value representing the address of an object  Every distinct object has a distinct address denoting the place in memory it lives  If it‟s possible to access an object it‟s possible to retrieve its address • For instance: x // if ‘x’ is an object x // then ‘x’ is the address of this object p // if ‘p’ is the address of an object p // then ‘p’ is the object itself 5 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Pointers • The „‟ is the addressof operator  Distinct from defining reference types • The „‟ is the dereference operator  Same as for any other iterator as well • If „p‟ contains the address of „x‟ we say that „the pointer p points to x‟ p x • Pointers are builtin data types which need to be initialized in order to be meaningful 6 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Pointers • Initialize to zero means „point to no object‟  Null pointer (special value, as no object has this address)  C++11: nullptr • Pointers have types  The address of an object of type T is „pointer to T‟  Written as: T • For instance: int x; // object of type int int p; // pointer to an int, p has type int int p; // pointer to an int, p has type int 7 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Pointers • A small (but full) example: int main() int x = 5; // p points to x int p = x; p x: 5 cout "x = " x endl; // change the value of x through p p x: 6 p = 6; cout "x = " x endl; return 0; 8 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Pointers • Think of pointers to be iterators • They point to the single object stored in a „virtual‟ (non existent) container 9 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Arrays • Part of the language rather than standard library  Hold sequence of elements of the same type  Size must be known at compile time  No member functions, no embedded typedefs  i.e. no sizetype member, use std::sizet instead • 3 dimensional point: double coords3; // or std::sizet const ndim = 3; double coordsndim; 10 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Arrays • Fundamental relationship between arrays and pointers  Name of the array is interpreted as a pointer to its first element: coords = 1.5; // set first element in coords to 1.5 11 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Pointer Arithmetic • Pointer is a randomaccess iterator  If „p‟ points to the mth element of an array, then  „p+n‟ points to the (m+n)th element of the array  „pn‟ points to the (mn)th element of the array • Further, as first element of array has number „0‟  coords+1 points to the second, and  coords+2 points to the third element  coords+3 points to the first element after the last • Possible to use standard algorithms with arrays: vectordouble v; copy(coords, coords + ndim, backinserter(v)); 12 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Pointer Arithmetic • Possible to initialize containers from arrays: vectordouble v(coords, coords + ndim); • More generally, wherever we used v.begin() and v.end(), we can use a and a+n (a: array, n: size) • If „p‟ and „q‟ are pointers  Then pq is the distance of the two pointers, which is the number of elements in between  Further (p – q) + q == p 13 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Indexing • If „p‟ points to the mth element of an array, then pn is the (m+n)th element, not its address • Consequently, if ‟a‟ is an array, and „n‟ an integer, then an refers to the nth element inside the array „a‟. • More formally, if „p‟ is a pointer, and „n‟ an integer, then pn is equivalent to (p+n) • In C++ indexing is not a property of arrays, but a corollary to the properties of pointers and arrays and the fact that pointers are random access iterators 14 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Array Initialization • Historically, arrays can be initialized easily: int const monthlengths = // we will deal elsewhere with leap years 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 ; • No size specified, it‟s automatically calculated • If size is specified, missing elements are set to zero (value initialized) • C++11 allows the same syntax for containers std::vectorint const monthlengths = // we will deal elsewhere with leap years 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 ; 15 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23String Literals Revisited • String literals are character arrays with a trailing zero byte • These are equivalent: char const hello = 'H', 'e', 'l', 'l', 'o', '\0' ; "Hello" • Null character is appended to be able to locate the end of the literal • Library has special functions dealing with „C‟ strings (string literals) 16 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23String Literals Revisited • Find the length of a string literal („C‟ string): strlen // Example implementation of standardlibrary function sizet strlen(char const p) sizet size = 0; while (p++ = '\0') ++size; return size; • Counting bytes (characters) excluding the null character 17 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23String Literals Revisited • Variable hello and literal “Hello” are equivalent: string s(hello); string s("Hello");  All will construct a string instance „s‟ holding “Hello” • Pointers are iterators: string s(hello, hello + strlen(hello)); 18 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Pointers and References • Think of a reference as an automatically dereferenced pointer  Or as “an alternative name for an object”  A reference must be initialized  The value of a reference cannot be changed after initialization int x = 7; int y = 8; int p = x; p = 9; p = y; // ok int r = x; r = 10; r = y; // error (and so is all other attempts to // change what r refers to) 19 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Arrays of Character Pointers • String literal is convenient way of writing address of first character of a null terminated string • Arrays can be initialized conveniently • Show how to initialize an array of character pointers from sequence of string literals • Grading (again sigh): If the grade is at least 97 94 90 87 84 80 77 74 70 60 0 Then the letter grade is A+ A A B+ B B C+ C C D F 20 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Arrays of Character Pointers string lettergrade(double grade) // range posts for numeric grades static double const numbers = 97, 94, 90, 87, 84, 80, 77, 74, 70, 60, 0 ; // names for the letter grades static char const const letters = "A+", "A", "A", "B+", "B", "B", "C+", "C", "C", "D", "F" ; // compute the number of grades given the size of the array // and the size of a single element static sizet const ngrades = sizeof(numbers)/sizeof(numbers0); // given a numeric grade, find and return the associated letter grade for (sizet i = 0; i ngrades; ++i) if (grade = numbersi) return lettersi; return "\\"; 21 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Arguments to main() • Command line arguments are optionally passed to main  Alternative prototype for main(): int main(int argc, char argv);  argc: number of arguments  argv: pointer to an array of character pointers, one argument each  At least one argument: the name of the executable itself, thus argc = 1 22 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Arguments to main() • Let‟s assume our executable is called „say‟ • Invoking it as say Hello, world • Should print: Hello, world int char char argc: 3 argv0 s a y \0 argv1 char H e , \0 l l o argv2 argv r l d \0 w o 23 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Arguments to main() int main(int argc, char argv) // if there are arguments, write them if (argc 1) int i; // declare i outside the for because we need // it after the loop finishes // write all but the last entry and a space for (i = 1; i argc1; ++i) cout argvi " "; // argvi is a char cout argvi endl; // write the last entry // but not a space return 0; 24 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Multiple Input Files • Print the content of all files given on command line to console: int main(int argc, char argv) int failcount = 0; // for each file in the input list for (int i = 1; i argc; ++i) ifstream in(argvi); // if it exists, write its contents, otherwise // generate an error message if (in) string s; while (getline(in, s)) cout s endl; else cerr "cannot open file " argvi endl; ++failcount; return failcount; 25 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23The Computer’s Memory • As a program sees it  Local variables “live on the stack”  Global variables are “static data”  The executable code are in “the code section” 26 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Three Kinds of Memory Management • Automatic memory management  Local variables  Allocated at the point of the definition  Deallocated at the end of the surrounding scope  Memory becomes invalid after that point: // this function deliberately yields an invalid pointer. // it is intended as a negative example—don't do this int invalidpointer() int x; return x; // instant disaster 27 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Three Kinds of Memory Management • Static memory management  Memory allocated once  Either at program startup (global variables)  Or when first encountered (functionstatic variables)  Deallocated at program termination: // This function is completely legitimate. int pointertostatic() static int x; return x;  Always returns pointer to same object 28 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Three Kinds of Memory Management • Dynamic memory management  Allocate an instance of T with „new T‟  Deallocate an existing instance pointed to by „p‟ with „delete p‟: int p = new int(42); // allocate int, initialize to 42 ++p; // p is now 43, same as ++(p) delete p; // delete int pointed to by p • Another example: int pointertodynamic() return new int(0); 29 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Allocating an Array • Arrays of type T are dynamically allocated using „new Tn‟, where n is the number of allocated elements • Deallocation of an array pointed to by p is done using „delete p‟ • „n‟ can be zero (Why) T p = new Tn; vectorT v(p, p + n); delete p; • Only way to create a dynamically sized array (remember, static array has to have size known at compile time) 30 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23A Problem: Memory Leak double calc(int resultsize, int max) double p = new doublemax; // allocate another max doubles // i.e., get max doubles from the free store double result = new doubleresultsize; // … use p to calculate results to be put in result … return result; double r = calc(200,100); // oops We ‚forgot‛ to give the memory // allocated for p back to the free store • Lack of deallocation (usually called "memory leaks") can be a serious problem in realworld programs • A program that must run for a long time can't afford any memory leaks 31 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23A Problem: Memory Leak double calc(int resultsize, int max) int p = new doublemax; // allocate max doubles // i.e., get max doubles from // the free store double result = new doubleresultsize; // … use p to calculate results to be put in result … delete p; // deallocate (free) that array // i.e., give the array back to the // free store return result; double r = calc(200,100); // use r delete r; // easy to forget 32 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Memory Leaks • A program that needs to run "forever" can't afford any memory leaks  An operating system is an example of a program that "runs forever" • If a function leaks 8 bytes every time it is called, how many days can it run before it has leaked/lost a megabyte  Trick question: not enough data to answer, but about 130,000 calls • All memory is returned to the system at the end of the program  If you run using an operating system (Windows, Unix, whatever) • Program that runs to completion with predictable memory usage may leak without causing problems  i.e., memory leaks aren't "good/bad" but they can be a problem in specific circumstances 33 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Memory Leaks • Another way to get a memory leak void f() st 1 value double p = new double27; // … p: p = new double42; // … delete p; nd 2 value // 1st array (of 27 doubles) leaked 34 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23Memory Leaks • How do we systematically and simply avoid memory leaks  Don't mess directly with new and delete  Use vector, etc.  Or use a garbage collector  A garbage collector is a program that keeps track of all of your allocations and returns unused freestore allocated memory to the free store (not covered in this course; see http://www.research.att.com/bs/C++.html)  Unfortunately, even a garbage collector doesn‟t prevent all leaks  Use RAII, see next lecture 35 CSC 1254, Spring 2015, Managing Memory 4/14/2015, Lectures 22, 23
Website URL
Comment