exam Flashcards
what does a profiler do
helps identify how long code takes to run
- functions that are called the most
- functions that run the longest
what are two reasons we may use way too much data
- sparse data sets
- lots of gaps/spaces - high volume of data
- should be compressed
what can we do to optimize space?
- compression
- bit manip
- choose better data structures
what is compression
analyzing the data to find and remove redundant or useless info
describe two types of compression
lossless - does not lose any info (zip, flac)
lossy - loses some info (jpeg, mp3)
with compression, what are we sacrificing? what are we improving?
explain.
we are sacrificing time to improve how much space we use.
- it takes extra time to compress, and to get the original data back
- it takes less space because compression gets rid of redundant or useless info
your program is taking too much space. what are your options to fix this problem and what should you try first?
- change data structure to something that fits the problem better
- bit manipulation if you need to squeeze out the last few bits
- compression
what type of variables should be used with bit manipulation? why?
unsigned variables
- unsigned variables can’t be negative
- overflow will be to 0
- bit manipulation is more reliable
what are the 3 steps to running a profiler
- compile code with flag
- gprof flag: -pg - run code
- run profiler
- gprof myCode
what are 4 key routes to optimize your code
- change algorithms
- restructure code
- redesign data structures
- refactor code
when and why should you optimize your code? When shouldn’t you?
only optimize if there’s a big performance issue. otherwise, the code is likely “good enough”
optimizing often makes code harder to:
- maintain
- reuse
- understand
optimizing code often makes the code harder to: (3)
- maintain
- reuse
- understand
what is the 80-20 rule and what concept does it relate to?
relates to optimization
80% of the program’s execution is spent in 20% of the code
optimizing is about making our code do ______(more/less) work, not making the current work __________(faster/slower)
less
faster
explain and give examples of optimizing by pre-computation
- pre-compute and store frequently used info in a table or variable
examples:
- constants (like PI or a BUFFER)
- the length of a string or array
explain optimizing by data structures
- select data structure that best applies to the problem. are insertions frequent? searches? sorted or not?
linked list
- fast insertions
array
- fast searches
- good for sequential processing
optimization by caching trades ____ for _____
trades storage for speed
malloc allocates a number of
____________ memory locations
the compiler ________ the type on the bits
contiguous
- an array
overlays
void pointers are addresses that point at ________
memory
garbage collection is a form of ____________ memory management.
it attempts to reclaim _____________ which is…
automatic
garbage. memory occupied by objects that are no longer in use
what does the type of a pointer actually do?
tells us how to interpret the data we find at the place in memory it points to
what are three methods of garbage collection?
- tracing
- mark and sweep. recursively determine which pointers are REACHABLE and then get rid of the ones that aren’t (NULL pointers can be reachable or unreachable) - reference counting
- keep track of how many references to an object are currently in use
- 0 refs = garbage - escape analysis
- compiler optimization technique
- objects that are not accessible outside of a function can get moved to the stack where they will automatically be claimed
when should we collect garbage?
asap (proactive)
only when necessary (lazy)
- not enough space
somewhere in between
what is fragmentation? how do we solve this?
when space in a program is used inefficiently
- there’s spaces between memory
defragmentation is used to reorganize and store data in contiguous memory
what is a class? what does it include?
- a blueprint to create objects
- includes data/info and behaviour
what is inheritance?
the traits a subclass gets from its parent
what is polymorphism? what’s a tool we can use in C to simulate polymorphism? examples?
polymorphism is an object that can take on various forms
we use “union”
examples:
- shapes (circle, square, triangle)
- a man (father, husband, employee)
the sizeof a union is the size of _____________
its widest type
what is the main difference between a union and structs? explain
only one property within the union can be used at a time
the members of a UNION are stored at the SAME address in memory. the members of a STRUCT are stored at DIFFERENT addresses
what is a function pointer?
show how you declare and initialize one
a function pointer contains the address of a function
int func1(int x); // function
int (*func1_ptr)(int x); // declare
func1_ptr = func1; // initialize
notes about initialization:
- no parentheses
- values are populated at linking stage
unions can be used to save ________ in structures.
explain how. examples?
space
if all the info inside a struct doesn’t apply to all uses of the struct, a union can be created within the struct to handle each specific case
example from slides: catalog item struct
- each item has a stock number, price, and item type
BUT
- books would have an author and a title variable
- a shirt would have colour, and size variables
- a mug would have colour, but may not have size
Unions can be used to create data structures that contain a mixture of data of different types. What can we use to differentiate between the types?
- a tag field
example from slides:
#define INT_KIND 0
#define DOUBLE_KIND 1
typedef struct {
int kind; /* tag field */
union {
int i;
double d;
} u;
} Number;
// assigning
n.kind = INT_KIND;
n.u.i = 82;
c supports 3 forms of pointer arithmetic. what are they?
adding an integer to a pointer
- if p points to a[i], then p + k points to a[i+k]
subtracting an integer from a pointer
- same thing but subtracting
subtracting one pointer from another: gives distance between the two elements
- if p points to a[i] and q points to a[k], then p - q is equal to i-k
you don’t have to cache Everything,
what should you cache? (2)
- you can cache the things that are used most
- cache the things that have been used recently (?)
