Changeset d83b266 for doc/theses


Ignore:
Timestamp:
Jul 26, 2021, 2:42:34 PM (4 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
0a061c0
Parents:
c86ee4c (diff), 98233b3 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Location:
doc/theses
Files:
8 added
24 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/andrew_beach_MMath/code/cond-catch.cfa

    rc86ee4c rd83b266  
    1919                throw_exception();
    2020        } catch (empty_exception * exc ; should_catch) {
    21                 // ...
     21                asm volatile ("# catch block (conditional)");
    2222        }
    2323}
    … …  
    3737                        cond_catch();
    3838                } catch (empty_exception * exc) {
    39                         // ...
     39                        asm volatile ("# catch block (unconditional)");
    4040                }
    4141        }

  • doc/theses/andrew_beach_MMath/code/cond-catch.cpp

    rc86ee4c rd83b266  
    1919                throw_exception();
    2020        } catch (EmptyException & exc) {
    21                 if (should_catch) {
     21                if (!should_catch) {
    2222                        throw;
    2323                }
     24                asm volatile ("# catch block (conditional)");
    2425        }
    2526}
    … …  
    3940                        cond_catch();
    4041                } catch (EmptyException &) {
    41                         // ...
     42                        asm volatile ("# catch block (unconditional)");
    4243                }
    4344    }

  • doc/theses/andrew_beach_MMath/code/cond-fixup.cfa

    rc86ee4c rd83b266  
    1212
    1313void throw_exception() {
    14         throw (empty_exception){&empty_vt};
     14        throwResume (empty_exception){&empty_vt};
    1515}
    1616
    … …  
    1818        try {
    1919                throw_exception();
    20         } catch (empty_exception * exc ; should_catch) {
    21                 // ...
     20        } catchResume (empty_exception * exc ; should_catch) {
     21                asm volatile ("# fixup block (conditional)");
    2222        }
    2323}
    … …  
    3636                try {
    3737                        cond_catch();
    38                 } catch (empty_exception * exc) {
    39                         // ...
     38                } catchResume (empty_exception * exc) {
     39                        asm volatile ("# fixup block (unconditional)");
    4040                }
    4141        }

  • doc/theses/andrew_beach_MMath/code/cross-catch.cfa

    rc86ee4c rd83b266  
    77EHM_EXCEPTION(not_raised_exception)();
    88
     9EHM_VIRTUAL_TABLE(not_raised_exception, not_vt);
     10
    911int main(int argc, char * argv[]) {
    1012        unsigned int times = 1;
    11         unsigned int total_frames = 1;
     13        volatile bool should_throw = false;
    1214        if (1 < argc) {
    1315                times = strtol(argv[1], 0p, 10);
    14         }
    15         if (2 < argc) {
    16                 total_frames = strtol(argv[2], 0p, 10);
    1716        }
    1817
    … …  
    2019        for (unsigned int count = 0 ; count < times ; ++count) {
    2120                try {
    22                         // ...
     21                        asm volatile ("# try block");
     22                        if (should_throw) {
     23                                throw (not_raised_exception){&not_vt};
     24                        }
    2325                } catch (not_raised_exception *) {
    24                         // ...
     26                        asm volatile ("# catch block");
    2527                }
    2628        }

  • doc/theses/andrew_beach_MMath/code/cross-catch.cpp

    rc86ee4c rd83b266  
    1111int main(int argc, char * argv[]) {
    1212        unsigned int times = 1;
     13        volatile bool should_throw = false;
    1314        if (1 < argc) {
    1415                times = strtol(argv[1], nullptr, 10);
    … …  
    1819        for (unsigned int count = 0 ; count < times ; ++count) {
    1920                try {
    20                         // ...
     21                        asm volatile ("# try block");
     22                        if (should_throw) {
     23                                throw NotRaisedException();
     24                        }
    2125                } catch (NotRaisedException &) {
    22                         // ...
     26                        asm volatile ("# catch block");
    2327                }
    2428        }

  • doc/theses/andrew_beach_MMath/code/cross-finally.cfa

    rc86ee4c rd83b266  
    55#include <stdlib.hfa>
    66
     7EHM_EXCEPTION(not_raised_exception)();
     8
     9EHM_VIRTUAL_TABLE(not_raised_exception, not_vt);
     10
    711int main(int argc, char * argv[]) {
    812        unsigned int times = 1;
    9         unsigned int total_frames = 1;
     13        volatile bool should_throw = false;
    1014        if (1 < argc) {
    1115                times = strtol(argv[1], 0p, 10);
    12         }
    13         if (2 < argc) {
    14                 total_frames = strtol(argv[2], 0p, 10);
    1516        }
    1617
    1718        Time start_time = timeHiRes();
    1819        for (unsigned int count = 0 ; count < times ; ++count) {
    19                  try {
    20                         // ...
     20                try {
     21                        asm volatile ("# try block");
     22                        if (should_throw) {
     23                                throw (not_raised_exception){&not_vt};
     24                        }
    2125                } finally {
    22                         // ...
     26                        asm volatile ("# finally block");
    2327                }
    2428        }

  • doc/theses/andrew_beach_MMath/code/cross-resume.cfa

    rc86ee4c rd83b266  
    2020        for (unsigned int count = 0 ; count < times ; ++count) {
    2121                try {
    22                         // ...
     22                        asm volatile ("");
    2323                } catchResume (not_raised_exception *) {
    24                         // ...
     24                        asm volatile ("");
    2525                }
    2626        }

  • doc/theses/andrew_beach_MMath/code/resume-detor.cfa

    rc86ee4c rd83b266  
    1212
    1313void ^?{}(WithDestructor & this) {
    14     // ...
     14        asm volatile ("# destructor body");
    1515}
    1616
    1717void unwind_destructor(unsigned int frames) {
    18     if (frames) {
     18        if (frames) {
    1919
    20         WithDestructor object;
    21         unwind_destructor(frames - 1);
    22     } else {
    23         throwResume (empty_exception){&empty_vt};
    24     }
     20                WithDestructor object;
     21                unwind_destructor(frames - 1);
     22        } else {
     23                throwResume (empty_exception){&empty_vt};
     24        }
    2525}
    2626
    … …  
    3636
    3737        Time start_time = timeHiRes();
    38     for (int count = 0 ; count < times ; ++count) {
    39         try {
    40             unwind_destructor(total_frames);
    41         } catchResume (empty_exception *) {
    42             // ...
    43         }
    44     }
     38        for (int count = 0 ; count < times ; ++count) {
     39                try {
     40                        unwind_destructor(total_frames);
     41                } catchResume (empty_exception *) {
     42                        asm volatile ("# fixup block");
     43                }
     44        }
    4545        Time end_time = timeHiRes();
    4646        sout | "Run-Time (ns): " | (end_time - start_time)`ns;

  • doc/theses/andrew_beach_MMath/code/resume-empty.cfa

    rc86ee4c rd83b266  
    1313                unwind_empty(frames - 1);
    1414        } else {
    15                 throw (empty_exception){&empty_vt};
     15                throwResume (empty_exception){&empty_vt};
    1616        }
    1717}
    … …  
    3131                try {
    3232                        unwind_empty(total_frames);
    33                 } catch (empty_exception *) {
    34                         // ...
     33                } catchResume (empty_exception *) {
     34                        asm volatile ("# fixup block");
    3535                }
    3636        }

  • doc/theses/andrew_beach_MMath/code/resume-finally.cfa

    rc86ee4c rd83b266  
    1414                        unwind_finally(frames - 1);
    1515                } finally {
    16                         // ...
     16                        asm volatile ("# finally block");
    1717                }
    1818        } else {
    … …  
    3636                        unwind_finally(total_frames);
    3737                } catchResume (empty_exception *) {
    38                         // ...
     38                        asm volatile ("# fixup block");
    3939                }
    4040        }

  • doc/theses/andrew_beach_MMath/code/resume-other.cfa

    rc86ee4c rd83b266  
    1616                        unwind_other(frames - 1);
    1717                } catchResume (not_raised_exception *) {
    18                         // ...
     18                        asm volatile ("# fixup block (stack)");
    1919                }
    2020        } else {
    … …  
    3838                        unwind_other(total_frames);
    3939                } catchResume (empty_exception *) {
    40                         // ...
     40                        asm volatile ("# fixup block (base)");
    4141                }
    4242        }

  • doc/theses/andrew_beach_MMath/code/test.sh

    rc86ee4c rd83b266  
    11#!/usr/bin/env bash
    22
    3 # Usage: LANGUAGE TEST | -b SOURCE_FILE
     3# Usage:
     4# test.sh LANGUAGE TEST
     5#   Run the TEST in LANGUAGE.
     6# test.sh -b SOURCE_FILE...
     7#   Build a test from SOURCE_FILE(s).
     8# test.sh -v LANGUAGE TEST FILE
     9#   View the result from TEST in LANGUAGE stored in FILE.
    410
    511readonly ITERATIONS=1000000 # 1 000 000, one million
    … …  
    1824        *.cfa)
    1925                # Requires a symbolic link.
    20                 mmake "${1%.cfa}" "$1" ./cfa "$1" -o "${1%.cfa}"
     26                mmake "${1%.cfa}" "$1" ./cfa -DNDEBUG -nodebug -O3 "$1" -o "${1%.cfa}"
    2127                ;;
    2228        *.cpp)
    23                 mmake "${1%.cpp}-cpp" "$1" g++ "$1" -o "${1%.cpp}-cpp"
     29                mmake "${1%.cpp}-cpp" "$1" g++ -DNDEBUG -O3 "$1" -o "${1%.cpp}-cpp"
    2430                ;;
    2531        *.java)
    … …  
    3844        done
    3945        exit 0
     46elif [ "-v" = "$1" -a 4 = "$#" ]; then
     47    TEST_LANG="$2"
     48    TEST_CASE="$3"
     49    VIEW_FILE="$4"
     50elif [ 2 -eq "$#" ]; then
     51        TEST_LANG="$1"
     52        TEST_CASE="$2"
     53else
     54        echo "Unknown call pattern." >&2
     55        exit 2
    4056fi
    4157
    … …  
    4662}
    4763
    48 case "$2" in
     64case "$TEST_CASE" in
    4965cond-match-all)
    5066        CFAT="./cond-catch $ITERATIONS 1"
    … …  
    5268        CPP="./cond-catch-cpp $ITERATIONS 1"
    5369        JAVA="java CondCatch $ITERATIONS 1"
     70        PYTHON="./cond_catch.py $ITERATIONS 1"
    5471        ;;
    5572cond-match-none)
    … …  
    5875        CPP="./cond-catch-cpp $ITERATIONS 0"
    5976        JAVA="java CondCatch $ITERATIONS 0"
     77        PYTHON="./cond_catch.py $ITERATIONS 0"
    6078        ;;
    6179cross-catch)
    … …  
    6482        CPP="./cross-catch-cpp $ITERATIONS"
    6583        JAVA="java CrossCatch $ITERATIONS"
     84        PYTHON="./cross_catch.py $ITERATIONS"
    6685        ;;
    6786cross-finally)
    … …  
    7089        CPP=unsupported
    7190        JAVA="java CrossFinally $ITERATIONS"
     91        PYTHON="./cross_finally.py $ITERATIONS"
    7292        ;;
    7393raise-detor)
    … …  
    7696        CPP="./throw-detor-cpp $ITERATIONS $STACK_HEIGHT"
    7797        JAVA=unsupported
     98        PYTHON=unsupported
    7899        ;;
    79100raise-empty)
    … …  
    82103        CPP="./throw-empty-cpp $ITERATIONS $STACK_HEIGHT"
    83104        JAVA="java ThrowEmpty $ITERATIONS $STACK_HEIGHT"
     105        PYTHON="./throw_empty.py $ITERATIONS $STACK_HEIGHT"
    84106        ;;
    85107raise-finally)
    … …  
    88110        CPP=unsupported
    89111        JAVA="java ThrowFinally $ITERATIONS $STACK_HEIGHT"
     112        PYTHON="./throw_finally.py $ITERATIONS $STACK_HEIGHT"
    90113        ;;
    91114raise-other)
    … …  
    94117        CPP="./throw-other-cpp $ITERATIONS $STACK_HEIGHT"
    95118        JAVA="java ThrowOther $ITERATIONS $STACK_HEIGHT"
     119        PYTHON="./throw_other.py $ITERATIONS $STACK_HEIGHT"
    96120        ;;
    97121*)
    98         echo "No such test." >&2
     122        echo "No such test: $TEST_CASE" >&2
    99123        exit 2
    100124        ;;
    101125esac
    102126
    103 case "$1" in
    104 cfa-t) echo $CFAT; $CFAT;;
    105 cfa-r) echo $CFAR; $CFAR;;
    106 cpp) echo $CPP; $CPP;;
    107 java) echo $JAVA; $JAVA;;
     127case "$TEST_LANG" in
     128cfa-t) CALL="$CFAT";;
     129cfa-r) CALL="$CFAR";;
     130cpp) CALL="$CPP";;
     131java) CALL="$JAVA";;
     132python) CALL="$PYTHON";;
     133*)
     134        echo "No such language: $TEST_LANG" >&2
     135        exit 2
     136        ;;
    108137esac
     138
     139echo $CALL
     140
     141if [ -n "$VIEW_FILE" ]; then
     142    grep -A 1 -B 0 "$CALL" "$VIEW_FILE" | sed -n -e 's!Run-Time (ns): !!;T;p'
     143    exit
     144fi
     145
     146$CALL

  • doc/theses/andrew_beach_MMath/code/throw-detor.cfa

    rc86ee4c rd83b266  
    1212
    1313void ^?{}(WithDestructor & this) {
    14         // ...
     14        asm volatile ("# destructor body");
    1515}
    1616
    … …  
    3939                        unwind_destructor(total_frames);
    4040                } catch (empty_exception *) {
    41                         // ...
     41                        asm volatile ("# catch block");
    4242                }
    4343        }

  • doc/theses/andrew_beach_MMath/code/throw-detor.cpp

    rc86ee4c rd83b266  
    1010
    1111struct WithDestructor {
    12         ~WithDestructor() {}
     12        ~WithDestructor() {
     13                asm volatile ("# destructor body");
     14        }
    1315};
    1416
    … …  
    3739                        unwind_destructor(total_frames);
    3840                } catch (EmptyException &) {
    39                         // ...
     41                        asm volatile ("# catch block");
    4042                }
    4143        }

  • doc/theses/andrew_beach_MMath/code/throw-empty.cfa

    rc86ee4c rd83b266  
    3232                        unwind_empty(total_frames);
    3333                } catch (empty_exception *) {
    34                         // ...
     34                        asm volatile ("# catch block");
    3535                }
    3636        }

  • doc/theses/andrew_beach_MMath/code/throw-empty.cpp

    rc86ee4c rd83b266  
    3232                        unwind_empty(total_frames);
    3333                } catch (EmptyException &) {
    34                         // ...
     34                        asm volatile ("# catch block");
    3535                }
    3636        }

  • doc/theses/andrew_beach_MMath/code/throw-finally.cfa

    rc86ee4c rd83b266  
    1414                        unwind_finally(frames - 1);
    1515                } finally {
    16                         // ...
     16                        asm volatile ("# finally block");
    1717                }
    1818        } else {
    … …  
    3636                        unwind_finally(total_frames);
    3737                } catch (empty_exception *) {
    38                         // ...
     38                        asm volatile ("# catch block");
    3939                }
    4040        }

  • doc/theses/andrew_beach_MMath/code/throw-other.cfa

    rc86ee4c rd83b266  
    1616                        unwind_other(frames - 1);
    1717                } catch (not_raised_exception *) {
    18                         // ...
     18                        asm volatile ("# catch block (stack)");
    1919                }
    2020        } else {
    … …  
    3838                        unwind_other(total_frames);
    3939                } catch (empty_exception *) {
    40                         // ...
     40                        asm volatile ("# catch block (base)");
    4141                }
    4242        }

  • doc/theses/andrew_beach_MMath/code/throw-other.cpp

    rc86ee4c rd83b266  
    1616                        unwind_other(frames - 1);
    1717                } catch (NotRaisedException &) {
    18                         // ...
     18                        asm volatile ("# catch block (stack)");
    1919                }
    2020        } else {
    … …  
    3838                        unwind_other(total_frames);
    3939                } catch (EmptyException &) {
    40                         // ...
     40                        asm volatile ("# catch block (base)");
    4141                }
    4242        }

  • doc/theses/andrew_beach_MMath/intro.tex

    rc86ee4c rd83b266  
    107107
    108108Exception handling is not a new concept,
    109 with papers on the subject dating back 70s.
    110 
    111 Their were popularised by \Cpp,
     109with papers on the subject dating back 70s.\cite{Goodenough}
     110
     111Early exceptions were often treated as signals. They carried no information
     112except their identity. Ada still uses this system.
     113
     114The modern flag-ship for termination exceptions is \Cpp,
    112115which added them in its first major wave of non-object-orientated features
    113116in 1990.
    114117% https://en.cppreference.com/w/cpp/language/history
    115 
    116 Java was the next popular language to use exceptions. It is also the most
    117 popular language with checked exceptions.
     118\Cpp has the ability to use any value of any type as an exception.
     119However that seems to immediately pushed aside for classes inherited from
     120\code{C++}{std::exception}.
     121Although there is a special catch-all syntax it does not allow anything to
     122be done with the caught value becuase nothing is known about it.
     123So instead a base type is defined with some common functionality (such as
     124the ability to describe the reason the exception was raised) and all
     125exceptions have that functionality.
     126This seems to be the standard now, as the garentied functionality is worth
     127any lost flexibility from limiting it to a single type.
     128
     129Java was the next popular language to use exceptions.
     130Its exception system largely reflects that of \Cpp, except that requires
     131you throw a child type of \code{Java}{java.lang.Throwable}
     132and it uses checked exceptions.
    118133Checked exceptions are part of the function interface they are raised from.
    119134This includes functions they propogate through, until a handler for that
    … …  
    131146Resumption exceptions have been much less popular.
    132147Although resumption has a history as old as termination's, very few
    133 programming languages have implement them.
     148programming languages have implemented them.
    134149% http://bitsavers.informatik.uni-stuttgart.de/pdf/xerox/parc/techReports/
    135150%   CSL-79-3_Mesa_Language_Manual_Version_5.0.pdf
    136 Mesa is one programming languages that did and experiance with that
    137 languages is quoted as being one of the reasons resumptions were not
     151Mesa is one programming languages that did. Experiance with Mesa
     152is quoted as being one of the reasons resumptions were not
    138153included in the \Cpp standard.
    139154% https://en.wikipedia.org/wiki/Exception_handling
    140 \todo{A comment about why we did include them when they are so unpopular
    141 might be approprate.}
    142 
    143 %\subsection
    144 Functional languages, tend to use solutions like the return union, but some
    145 exception-like constructs still appear.
    146 
    147 For instance Haskell's built in error mechanism can make the result of any
    148 expression, including function calls. Any expression that examines an
    149 error value will in-turn produce an error. This continues until the main
    150 function produces an error or until it is handled by one of the catch
    151 functions.
     155Since then resumptions have been ignored in the main-stream.
     156
     157All of this does call into question the use of resumptions, is
     158something largely rejected decades ago worth revisiting now?
     159Yes, even if it was the right call at the time there have been decades
     160of other developments in computer science that have changed the situation
     161since then.
     162Some of these developments, such as in functional programming's resumption
     163equivalent: algebraic effects\cite{Zhang19}, are directly related to
     164resumptions as well.
     165A complete rexamination of resumptions is beyond a single paper, but it is
     166enough to try them again in \CFA.
     167% Especially considering how much easier they are to implement than
     168% termination exceptions.
     169
     170%\subsection
     171Functional languages tend to use other solutions for their primary error
     172handling mechanism, exception-like constructs still appear.
     173Termination appears in error construct, which marks the result of an
     174expression as an error, the result of any expression that tries to use it as
     175an error, and so on until an approprate handler is reached.
     176Resumption appears in algebric effects, where a function dispatches its
     177side-effects to its caller for handling.
    152178
    153179%\subsection
    154180More recently exceptions seem to be vanishing from newer programming
    155 languages.
    156 Rust and Go reduce this feature to panics.
    157 Panicing is somewhere between a termination exception and a program abort.
    158 Notably in Rust a panic can trigger either, a panic may unwind the stack or
    159 simply kill the process.
     181languages, replaced by ``panic".
     182In Rust a panic is just a program level abort that may be implemented by
     183unwinding the stack like in termination exception handling.
    160184% https://doc.rust-lang.org/std/panic/fn.catch_unwind.html
    161 Go's panic is much more similar to a termination exception but there is
    162 only a catch-all function with \code{Go}{recover()}.
    163 So exceptions still are appearing, just in reduced forms.
     185Go's panic through is very similar to a termination except it only supports
     186a catch-all by calling \code{Go}{recover()}, simplifying the interface at
     187the cost of flexability.
    164188
    165189%\subsection

  • doc/theses/andrew_beach_MMath/performance.tex

    rc86ee4c rd83b266  
    11\chapter{Performance}
    22\label{c:performance}
    3 
    4 \textbf{Just because of the stage of testing there are design notes for
    5 the tests as well as commentary on them.}
    63
    74Performance has been of secondary importance for most of this project.
    … …  
    118
    129\section{Test Set-Up}
    13 Tests will be run on \CFA, C++ and Java.
     10Tests will be run in \CFA, C++, Java and Python.
     11In addition there are two sets of tests for \CFA,
     12one for termination exceptions and once with resumption exceptions.
    1413
    1514C++ is the most comparable language because both it and \CFA use the same
    … …  
    1817comparison. \CFA's EHM has had significantly less time to be optimized and
    1918does not generate its own assembly. It does have a slight advantage in that
    20 there are some features it does not handle.
     19there are some features it does not handle, through utility functions,
     20but otherwise \Cpp has a significant advantage.
    2121
    2222Java is another very popular language with similar termination semantics.
    … …  
    2525It also implements the finally clause on try blocks allowing for a direct
    2626feature-to-feature comparison.
     27As with \Cpp, Java's implementation is more mature, has more optimizations
     28and more extra features.
     29
     30Python was used as a point of comparison because of the \CFA EHM's
     31current performance goals, which is not be prohibitively slow while the
     32features are designed and examined. Python has similar performance goals for
     33creating quick scripts and its wide use suggests it has achieved those goals.
     34
     35Unfortunately there are no notable modern programming languages with
     36resumption exceptions. Even the older programming languages with resumptions
     37seem to be notable only for having resumptions.
     38So instead resumptions are compared to a less similar but much more familiar
     39feature, termination exceptions.
    2740
    2841All tests are run inside a main loop which will perform the test
    2942repeatedly. This is to avoids start-up or tear-down time from
    3043affecting the timing results.
    31 A consequence of this is that tests cannot terminate the program,
    32 which does limit how tests can be implemented.
    33 There are catch-alls to keep unhandled
    34 exceptions from terminating tests.
     44Most test were run 1 000 000 (a million) times.
     45The Java versions of the test also run this loop an extra 1000 times before
     46beginning to time the results to ``warm-up" the JVM.
     47
     48Timing is done internally, with time measured immediately before and
     49immediately after the test loop. The difference is calculated and printed.
     50
     51The loop structure and internal timing means it is impossible to test
     52unhandled exceptions in \Cpp and Java as that would cause the process to
     53terminate.
     54Luckily, performance on the ``give-up and kill the process" path is not
     55critical.
    3556
    3657The exceptions used in these tests will always be a exception based off of
    3758the base exception. This requirement minimizes performance differences based
    38 on the object model.
    39 Catch-alls are done by catching the root exception type (not using \Cpp's
    40 \code{C++}{catch(...)}).
     59on the object model used to repersent the exception.
    4160
    42 Tests run in Java were not warmed because exception code paths should not be
    43 hot.
     61All tests were designed to be as minimal as possible while still preventing
     62exessive optimizations.
     63For example, empty inline assembly blocks are used in \CFA and \Cpp to
     64prevent excessive optimizations while adding no actual work.
     65
     66% We don't use catch-alls but if we did:
     67% Catch-alls are done by catching the root exception type (not using \Cpp's
     68% \code{C++}{catch(...)}).
    4469
    4570\section{Tests}
    … …  
    4772components of the exception system.
    4873The should provide a guide as to where the EHM's costs can be found.
    49 
    50 Tests are run in \CFA, \Cpp and Java.
    51 Not every test is run in every language, if the feature under test is missing
    52 the test is skipped. These cases will be noted.
    53 In addition to the termination tests for every language,
    54 \CFA has a second set of tests that test resumption. These are the same
    55 except that the raise statements and handler clauses are replaced with the
    56 resumption variants.
    5774
    5875\paragraph{Raise and Handle}
    … …  
    6279start-up and shutdown on the results.
    6380Each iteration of the main loop
    64 \begin{itemize}
     81\begin{itemize}[nosep]
    6582\item Empty Function:
    6683The repeating function is empty except for the necessary control code.
    … …  
    6885The repeating function creates an object with a destructor before calling
    6986itself.
    70 (Java is skipped as it does not destructors.)
    7187\item Finally:
    7288The repeating function calls itself inside a try block with a finally clause
    7389attached.
    74 (\Cpp is skipped as it does not have finally clauses.)
    7590\item Other Handler:
    7691The repeating function calls itself inside a try block with a handler that
    … …  
    8499In each iteration, a try statement is executed. Entering and leaving a loop
    85100is all the test wants to do.
    86 \begin{itemize}
     101\begin{itemize}[nosep]
    87102\item Handler:
    88103The try statement has a handler (of the matching kind).
    … …  
    95110Only \CFA implements the language level conditional match,
    96111the other languages must mimic with an ``unconditional" match (it still
    97 checks the exception's type) and conditional re-raise.
    98 \begin{itemize}
    99 \item Catch All:
     112checks the exception's type) and conditional re-raise if it was not supposed
     113to handle that exception.
     114\begin{itemize}[nosep]
     115\item Match All:
    100116The condition is always true. (Always matches or never re-raises.)
    101 \item Catch None:
     117\item Match None:
    102118The condition is always false. (Never matches or always re-raises.)
    103119\end{itemize}
    … …  
    113129%related to -fexceptions.)
    114130
    115 % Some languages I left out:
    116 % Python: Its a scripting language, different
    117 % uC++: Not well known and should the same results as C++, except for
    118 %   resumption which should be the same.
     131\section{Results}
     132Each test is was run five times, the best and worst result were discarded and
     133the remaining values were averaged.
    119134
    120 %\section{Resumption Comparison}
    121 \todo{Can we find a good language to compare resumptions in.}
     135In cases where a feature is not supported by a language the test is skipped
     136for that language. Similarly, if a test is does not change between resumption
     137and termination in \CFA, then only one test is written and the result
     138was put into the termination column.
     139
     140\begin{tabular}{|l|c c c c c|}
     141\hline
     142              & \CFA (Terminate) & \CFA (Resume) & \Cpp & Java & Python \\
     143\hline
     144Raise Empty   & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
     145Raise D'tor   & 0.0 & 0.0 & 0.0 & N/A & N/A \\
     146Raise Finally & 0.0 & 0.0 & N/A & 0.0 & 0.0 \\
     147Raise Other   & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
     148Cross Handler & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
     149Cross Finally & 0.0 & N/A & N/A & 0.0 & 0.0 \\
     150Match All     & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
     151Match None    & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 \\
     152\hline
     153\end{tabular}

  • doc/theses/mubeen_zulfiqar_MMath/allocator.tex

    rc86ee4c rd83b266  
    4444
    4545\subsection{Design philosophy}
    46 
     46The objective of uHeapLmmm's new design was to fulfill following requirements:
     47\begin{itemize}
     48\item It should be concurrent to be used in multi-threaded programs.
     49\item It should avoid global locks, on resources shared across all threads, as much as possible.
     50\item It's performance (FIX ME: cite performance benchmarks) should be comparable to the commonly used allocators (FIX ME: cite common allocators).
     51\item It should be a lightweight memory allocator.
     52\end{itemize}
    4753
    4854%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    4955
    5056\section{Background and previous design of uHeapLmmm}
    51 
     57uHeapLmmm was originally designed by X in X (FIX ME: add original author after confirming with Peter).
     58(FIX ME: make and add figure of previous design with description)
    5259
    5360%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    5461
    5562\section{Distributed design of uHeapLmmm}
    56 
    57 
    58 \subsection{Advantages of distributed design}
    59 
    60 
    61 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    62 
    63 \section{Added Features}
    64 
    65 
    66 \subsection{Methods}
    67 Why did we need it?
    68 The added benefits.
    69 
    70 
    71 \subsection{Alloc Interface}
    72 Why did we need it?
    73 The added benefits.
    74 
    75 
    76 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    77 % Following is added by Peter
    78 
    79 \noindent
    80 ====================
    81 
    82 \newpage
     63uHeapLmmm's design was reviewed and changed to fulfill new requirements (FIX ME: cite allocator philosophy). For this purpose, following two designs of uHeapLmm were proposed:
     64
    8365\paragraph{Design 1: Decentralized}
    8466Fixed number of heaps: shard the heap into N heaps each with a bump-area allocated from the @sbrk@ area.
    … …  
    9274\input{AllocDS1}
    9375\end{cquote}
    94 Problems: need to know when a KT is created and destroyed to know when to create/delete the KT's heap.
    95 On KT deletion, its heap freed-storage needs to be distributed somewhere.
     76Problems: need to know when a KT is created and destroyed to know when to assign/un-assign a heap to the KT.
    9677
    9778\paragraph{Design 2: Centralized}
    98 
    9979One heap, but lower bucket sizes are N-shared across KTs.
    10080This design leverages the fact that 95\% of allocation requests are less than 512 bytes and there are only 3--5 different request sizes.
    … …  
    10787\end{cquote}
    10888Problems: need to know when a kernel thread (KT) is created and destroyed to know when to assign a shared bucket-number.
    109 When no thread is assigned a bucket number, its free storage is unavailable.
     89When no thread is assigned a bucket number, its free storage is unavailable. All KTs will be contended for one lock on sbrk for their initial allocations (before free-lists gets populated).
     90
     91Out of the two designs, Design 1 was chosen because it's concurrency is better across all bucket-sizes as design-2 shards a few buckets of selected sizes while design-1 shards all the buckets. Design-2 shards the whole heap which has all the buckets with the addition of sharding sbrk area.
     92
     93\subsection{Advantages of distributed design}
     94The distributed design of uHeapLmmm is concurrent to work in multi-threaded applications.
     95
     96Some key benefits of the distributed design of uHeapLmmm are as follows:
     97
     98\begin{itemize}
     99\item
     100The bump allocation is concurrent as memory taken from sbrk is sharded across all heaps as bump allocation reserve. The lock on bump allocation (on memory taken from sbrk) will only be contended if KTs > N. The contention on sbrk area is less likely as it will only happen in the case if heaps assigned to two KTs get short of bump allocation reserve simultanously.
     101\item
     102N heaps are created at the start of the program and destroyed at the end of program. When a KT is created, we only assign it to one of the heaps. When a KT is destroyed, we only dissociate it from the assigned heap but we do not destroy that heap. That heap will go back to our pool-of-heaps, ready to be used by some new KT. And if that heap was shared among multiple KTs (like the case of KTs > N) then, on deletion of one KT, that heap will be still in-use of the other KTs. This will prevent creation and deletion of heaps during run-time as heaps are re-usable which helps in keeping low-memory footprint.
     103\item
    110104It is possible to use sharing and stealing techniques to share/find unused storage, when a free list is unused or empty.
     105\item
     106Distributed design avoids unnecassry locks on resources shared across all KTs.
     107\end{itemize}
     108
     109FIX ME: Cite performance comparison of the two heap designs if required
     110
     111%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     112
     113\section{Added Features and Methods}
     114To improve the UHeapLmmm allocator (FIX ME: cite uHeapLmmm) interface and make it more user friendly, we added a few more routines to the C allocator. Also, we built a CFA (FIX ME: cite cforall) interface on top of C interface to increase the usability of the allocator.
     115
     116\subsection{C Interface}
     117We added a few more features and routines to the allocator's C interface that can make the allocator more usable to the programmers. THese features will programmer more control on the dynamic memory allocation.
     118
     119\subsubsection void * aalloc( size_t dim, size_t elemSize )
     120aalloc is an extension of malloc. It allows programmer to allocate a dynamic array of objects without calculating the total size of array explicitly. The only alternate of this routine in the other allocators is calloc but calloc also fills the dynamic memory with 0 which makes it slower for a programmer who only wants to dynamically allocate an array of objects without filling it with 0.
     121\paragraph{Usage}
     122aalloc takes two parameters.
     123\begin{itemize}
     124\item
     125dim: number of objects in the array
     126\item
     127elemSize: size of the object in the array.
     128\end{itemize}
     129It returns address of dynamic object allocatoed on heap that can contain dim number of objects of the size elemSize. On failure, it returns NULL pointer.
     130
     131\subsubsection void * resize( void * oaddr, size_t size )
     132resize is an extension of relloc. It allows programmer to reuse a cuurently allocated dynamic object with a new size requirement. Its alternate in the other allocators is realloc but relloc also copy the data in old object to the new object which makes it slower for the programmer who only wants to reuse an old dynamic object for a new size requirement but does not want to preserve the data in the old object to the new object.
     133\paragraph{Usage}
     134resize takes two parameters.
     135\begin{itemize}
     136\item
     137oaddr: the address of the old object that needs to be resized.
     138\item
     139size: the new size requirement of the to which the old object needs to be resized.
     140\end{itemize}
     141It returns an object that is of the size given but it does not preserve the data in the old object. On failure, it returns NULL pointer.
     142
     143\subsubsection void * resize( void * oaddr, size_t nalign, size_t size )
     144This resize is an extension of the above resize (FIX ME: cite above resize). In addition to resizing the size of of an old object, it can also realign the old object to a new alignment requirement.
     145\paragraph{Usage}
     146This resize takes three parameters. It takes an additional parameter of nalign as compared to the above resize (FIX ME: cite above resize).
     147\begin{itemize}
     148\item
     149oaddr: the address of the old object that needs to be resized.
     150\item
     151nalign: the new alignment to which the old object needs to be realigned.
     152\item
     153size: the new size requirement of the to which the old object needs to be resized.
     154\end{itemize}
     155It returns an object with the size and alignment given in the parameters. On failure, it returns a NULL pointer.
     156
     157\subsubsection void * amemalign( size_t alignment, size_t dim, size_t elemSize )
     158amemalign is a hybrid of memalign and aalloc. It allows programmer to allocate an aligned dynamic array of objects without calculating the total size of the array explicitly. It frees the programmer from calculating the total size of the array.
     159\paragraph{Usage}
     160amemalign takes three parameters.
     161\begin{itemize}
     162\item
     163alignment: the alignment to which the dynamic array needs to be aligned.
     164\item
     165dim: number of objects in the array
     166\item
     167elemSize: size of the object in the array.
     168\end{itemize}
     169It returns a dynamic array of objects that has the capacity to contain dim number of objects of the size of elemSize. The returned dynamic array is aligned to the given alignment. On failure, it returns NULL pointer.
     170
     171\subsubsection void * cmemalign( size_t alignment, size_t dim, size_t elemSize )
     172cmemalign is a hybrid of amemalign and calloc. It allows programmer to allocate an aligned dynamic array of objects that is 0 filled. The current way to do this in other allocators is to allocate an aligned object with memalign and then fill it with 0 explicitly. This routine provides both features of aligning and 0 filling, implicitly.
     173\paragraph{Usage}
     174cmemalign takes three parameters.
     175\begin{itemize}
     176\item
     177alignment: the alignment to which the dynamic array needs to be aligned.
     178\item
     179dim: number of objects in the array
     180\item
     181elemSize: size of the object in the array.
     182\end{itemize}
     183It returns a dynamic array of objects that has the capacity to contain dim number of objects of the size of elemSize. The returned dynamic array is aligned to the given alignment and is 0 filled. On failure, it returns NULL pointer.
     184
     185\subsubsection size_t malloc_alignment( void * addr )
     186malloc_alignment returns the alignment of a currently allocated dynamic object. It allows the programmer in memory management and personal bookkeeping. It helps the programmer in verofying the alignment of a dynamic object especially in a scenerio similar to prudcer-consumer where a producer allocates a dynamic object and the consumer needs to assure that the dynamic object was allocated with the required alignment.
     187\paragraph{Usage}
     188malloc_alignment takes one parameters.
     189\begin{itemize}
     190\item
     191addr: the address of the currently allocated dynamic object.
     192\end{itemize}
     193malloc_alignment returns the alignment of the given dynamic object. On failure, it return the value of default alignment of the uHeapLmmm allocator.
     194
     195\subsubsection bool malloc_zero_fill( void * addr )
     196malloc_zero_fill returns whether a currently allocated dynamic object was initially zero filled at the time of allocation. It allows the programmer in memory management and personal bookkeeping. It helps the programmer in verifying the zero filled property of a dynamic object especially in a scenerio similar to prudcer-consumer where a producer allocates a dynamic object and the consumer needs to assure that the dynamic object was zero filled at the time of allocation.
     197\paragraph{Usage}
     198malloc_zero_fill takes one parameters.
     199\begin{itemize}
     200\item
     201addr: the address of the currently allocated dynamic object.
     202\end{itemize}
     203malloc_zero_fill returns true if the dynamic object was initially zero filled and return false otherwise. On failure, it returns false.
     204
     205\subsubsection size_t malloc_size( void * addr )
     206malloc_size returns the allocation size of a currently allocated dynamic object. It allows the programmer in memory management and personal bookkeeping. It helps the programmer in verofying the alignment of a dynamic object especially in a scenerio similar to prudcer-consumer where a producer allocates a dynamic object and the consumer needs to assure that the dynamic object was allocated with the required size. Its current alternate in the other allocators is malloc_usable_size. But, malloc_size is different from malloc_usable_size as malloc_usabe_size returns the total data capacity of dynamic object including the extra space at the end of the dynamic object. On the other hand, malloc_size returns the size that was given to the allocator at the allocation of the dynamic object. This size is updated when an object is realloced, resized, or passed through a similar allocator routine.
     207\paragraph{Usage}
     208malloc_size takes one parameters.
     209\begin{itemize}
     210\item
     211addr: the address of the currently allocated dynamic object.
     212\end{itemize}
     213malloc_size returns the allocation size of the given dynamic object. On failure, it return zero.
     214
     215\subsubsection void * realloc( void * oaddr, size_t nalign, size_t size )
     216This realloc is an extension of the default realloc (FIX ME: cite default realloc). In addition to reallocating an old object and preserving the data in old object, it can also realign the old object to a new alignment requirement.
     217\paragraph{Usage}
     218This realloc takes three parameters. It takes an additional parameter of nalign as compared to the default realloc.
     219\begin{itemize}
     220\item
     221oaddr: the address of the old object that needs to be reallocated.
     222\item
     223nalign: the new alignment to which the old object needs to be realigned.
     224\item
     225size: the new size requirement of the to which the old object needs to be resized.
     226\end{itemize}
     227It returns an object with the size and alignment given in the parameters that preserves the data in the old object. On failure, it returns a NULL pointer.
     228
     229\subsection{CFA Malloc Interface}
     230We added some routines to the malloc interface of CFA. These routines can only be used in CFA and not in our standalone uHeapLmmm allocator as these routines use some features that are only provided by CFA and not by C. It makes the allocator even more usable to the programmers.
     231CFA provides the liberty to know the returned type of a call to the allocator. So, mainly in these added routines, we removed the object size parameter from the routine as allocator can calculate the size of the object from the returned type.
     232
     233\subsubsection T * malloc( void )
     234This malloc is a simplified polymorphic form of defualt malloc (FIX ME: cite malloc). It does not take any parameter as compared to default malloc that takes one parameter.
     235\paragraph{Usage}
     236This malloc takes no parameters.
     237It returns a dynamic object of the size of type T. On failure, it return NULL pointer.
     238
     239\subsubsection T * aalloc( size_t dim )
     240This aalloc is a simplified polymorphic form of above aalloc (FIX ME: cite aalloc). It takes one parameter as compared to the above aalloc that takes two parameters.
     241\paragraph{Usage}
     242aalloc takes one parameters.
     243\begin{itemize}
     244\item
     245dim: required number of objects in the array.
     246\end{itemize}
     247It returns a dynamic object that has the capacity to contain dim number of objects, each of the size of type T. On failure, it return NULL pointer.
     248
     249\subsubsection T * calloc( size_t dim )
     250This calloc is a simplified polymorphic form of defualt calloc (FIX ME: cite calloc). It takes one parameter as compared to the default calloc that takes two parameters.
     251\paragraph{Usage}
     252This calloc takes one parameter.
     253\begin{itemize}
     254\item
     255dim: required number of objects in the array.
     256\end{itemize}
     257It returns a dynamic object that has the capacity to contain dim number of objects, each of the size of type T. On failure, it return NULL pointer.
     258
     259\subsubsection T * resize( T * ptr, size_t size )
     260This resize is a simplified polymorphic form of above resize (FIX ME: cite resize with alignment). It takes two parameters as compared to the above resize that takes three parameters. It frees the programmer from explicitly mentioning the alignment of the allocation as CFA provides gives allocator the liberty to get the alignment of the returned type.
     261\paragraph{Usage}
     262This resize takes two parameters.
     263\begin{itemize}
     264\item
     265ptr: address of the old object.
     266\item
     267size: the required size of the new object.
     268\end{itemize}
     269It returns a dynamic object of the size given in paramters. The returned object is aligned to the alignemtn of type T. On failure, it return NULL pointer.
     270
     271\subsubsection T * realloc( T * ptr, size_t size )
     272This realloc is a simplified polymorphic form of defualt realloc (FIX ME: cite realloc with align). It takes two parameters as compared to the above realloc that takes three parameters. It frees the programmer from explicitly mentioning the alignment of the allocation as CFA provides gives allocator the liberty to get the alignment of the returned type.
     273\paragraph{Usage}
     274This realloc takes two parameters.
     275\begin{itemize}
     276\item
     277ptr: address of the old object.
     278\item
     279size: the required size of the new object.
     280\end{itemize}
     281It returns a dynamic object of the size given in paramters that preserves the data in the given object. The returned object is aligned to the alignemtn of type T. On failure, it return NULL pointer.
     282
     283\subsubsection T * memalign( size_t align )
     284This memalign is a simplified polymorphic form of defualt memalign (FIX ME: cite memalign). It takes one parameters as compared to the default memalign that takes two parameters.
     285\paragraph{Usage}
     286memalign takes one parameters.
     287\begin{itemize}
     288\item
     289align: the required alignment of the dynamic object.
     290\end{itemize}
     291It returns a dynamic object of the size of type T that is aligned to given parameter align. On failure, it return NULL pointer.
     292
     293\subsubsection T * amemalign( size_t align, size_t dim )
     294This amemalign is a simplified polymorphic form of above amemalign (FIX ME: cite amemalign). It takes two parameter as compared to the above amemalign that takes three parameters.
     295\paragraph{Usage}
     296amemalign takes two parameters.
     297\begin{itemize}
     298\item
     299align: required alignment of the dynamic array.
     300\item
     301dim: required number of objects in the array.
     302\end{itemize}
     303It returns a dynamic object that has the capacity to contain dim number of objects, each of the size of type T. The returned object is aligned to the given parameter align. On failure, it return NULL pointer.
     304
     305\subsubsection T * cmemalign( size_t align, size_t dim  )
     306This cmemalign is a simplified polymorphic form of above cmemalign (FIX ME: cite cmemalign). It takes two parameter as compared to the above cmemalign that takes three parameters.
     307\paragraph{Usage}
     308cmemalign takes two parameters.
     309\begin{itemize}
     310\item
     311align: required alignment of the dynamic array.
     312\item
     313dim: required number of objects in the array.
     314\end{itemize}
     315It returns a dynamic object that has the capacity to contain dim number of objects, each of the size of type T. The returned object is aligned to the given parameter align and is zero filled. On failure, it return NULL pointer.
     316
     317\subsubsection T * aligned_alloc( size_t align )
     318This aligned_alloc is a simplified polymorphic form of defualt aligned_alloc (FIX ME: cite aligned_alloc). It takes one parameter as compared to the default aligned_alloc that takes two parameters.
     319\paragraph{Usage}
     320This aligned_alloc takes one parameter.
     321\begin{itemize}
     322\item
     323align: required alignment of the dynamic object.
     324\end{itemize}
     325It returns a dynamic object of the size of type T that is aligned to the given parameter. On failure, it return NULL pointer.
     326
     327\subsubsection int posix_memalign( T ** ptr, size_t align )
     328This posix_memalign is a simplified polymorphic form of defualt posix_memalign (FIX ME: cite posix_memalign). It takes two parameters as compared to the default posix_memalign that takes three parameters.
     329\paragraph{Usage}
     330This posix_memalign takes two parameter.
     331\begin{itemize}
     332\item
     333ptr: variable address to store the address of the allocated object.
     334\item
     335align: required alignment of the dynamic object.
     336\end{itemize}
     337It stores address of the dynamic object of the size of type T in given parameter ptr. This object is aligned to the given parameter. On failure, it return NULL pointer.
     338
     339\subsubsection T * valloc( void )
     340This valloc is a simplified polymorphic form of defualt valloc (FIX ME: cite valloc). It takes no parameters as compared to the default valloc that takes one parameter.
     341\paragraph{Usage}
     342valloc takes no parameters.
     343It returns a dynamic object of the size of type T that is aligned to the page size. On failure, it return NULL pointer.
     344
     345\subsubsection T * pvalloc( void )
     346This pcvalloc is a simplified polymorphic form of defualt pcvalloc (FIX ME: cite pcvalloc). It takes no parameters as compared to the default pcvalloc that takes one parameter.
     347\paragraph{Usage}
     348pvalloc takes no parameters.
     349It returns a dynamic object of the size that is calcutaed by rouding the size of type T. The returned object is also aligned to the page size. On failure, it return NULL pointer.
     350
     351\subsection{Alloc Interface}
     352In addition to improve allocator interface both for CFA and our standalone allocator uHeapLmmm in C. We also added a new alloc interface in CFA that increases usability of dynamic memory allocation.
     353This interface helps programmers in three major ways.
     354\begin{itemize}
     355\item
     356Routine Name: alloc interfce frees programmers from remmebring different routine names for different kind of dynamic allocations.
     357\item
     358Parametre Positions: alloc interface frees programmers from remembering parameter postions in call to routines.
     359\item
     360Object Size: alloc interface does not require programmer to mention the object size as CFA allows allocator to determince the object size from returned type of alloc call.
     361\end{itemize}
     362
     363Alloc interface uses polymorphism, backtick routines (FIX ME: cite backtick) and ttype parameters of CFA (FIX ME: cite ttype) to provide a very simple dynamic memory allocation interface to the programmers. The new interfece has just one routine name alloc that can be used to perform a wide range of dynamic allocations. The parameters use backtick functions to provide a similar-to named parameters feature for our alloc interface so that programmers do not have to remember parameter positions in alloc call except the position of dimension (dim) parameter.
     364
     365\subsubsection{Routine: T * alloc( ... )}
     366Call to alloc wihout any parameter returns one object of size of type T allocated dynamically.
     367Only the dimension (dim) parameter for array allocation has the fixed position in the alloc routine. If programmer wants to allocate an array of objects that the required number of members in the array has to be given as the first parameter to the alloc routine.
     368alocc routine accepts six kinds of arguments. Using different combinations of tha parameters, different kind of allocations can be performed. Any combincation of parameters can be used together except `realloc and `resize that should not be used simultanously in one call to routine as it creates ambiguity about whether to reallocate or resize a currently allocated dynamic object. If both `resize and `realloc are used in a call to alloc then the latter one will take effect or unexpected resulted might be produced.
     369
     370\paragraph{Dim}
     371This is the only parameter in the alloc routine that has a fixed-position and it is also the only parameter that does not use a backtick function. It has to be passed at the first position to alloc call in-case of an array allocation of objects of type T.
     372It represents the required number of members in the array allocation as in CFA's aalloc (FIX ME: cite aalloc).
     373This parameter should be of type size_t.
     374
     375Example: int a = alloc( 5 )
     376This call will return a dynamic array of five integers.
     377
     378\paragraph{Align}
     379This parameter is position-free and uses a backtick routine align (`align). The parameter passed with `align should be of type size_t. If the alignment parameter is not a power of two or is less than the default alignment of the allocator (that can be found out using routine libAlign in CFA) then the passed alignment parameter will be rejected and the default alignment will be used.
     380
     381Example: int b = alloc( 5 , 64`align )
     382This call will return a dynamic array of five integers. It will align the allocated object to 64.
     383
     384\paragraph{Fill}
     385This parameter is position-free and uses a backtick routine fill (`fill). In case of realloc, only the extra space after copying the data in the old object will be filled with given parameter.
     386Three types of parameters can be passed using `fill.
     387\begin{itemize}
     388\item
     389char: A char can be passed with `fill to fill the whole dynamic allocation with the given char recursively till the end of required allocation.
     390\item
     391Object of returned type: An object of type of returned type can be passed with `fill to fill the whole dynamic allocation with the given object recursively till the end of required allocation.
     392\item
     393Dynamic object of returned type: A dynamic object of type of returned type can be passed with `fill to fill the dynamic allocation with the given dynamic object. In this case, the allocated memory is not filled recursively till the end of allocation. The filling happen untill the end object passed to `fill or the end of requested allocation reaches.
     394\end{itemize}
     395
     396Example: int b = alloc( 5 , 'a'`fill )
     397This call will return a dynamic array of five integers. It will fill the allocated object with character 'a' recursively till the end of requested allocation size.
     398
     399Example: int b = alloc( 5 , 4`fill )
     400This call will return a dynamic array of five integers. It will fill the allocated object with integer 4 recursively till the end of requested allocation size.
     401
     402Example: int b = alloc( 5 , a`fill ) where a is a pointer of int type
     403This call will return a dynamic array of five integers. It will copy data in a to the returned object non-recursively untill end of a or the newly allocated object is reached.
     404
     405\paragraph{Resize}
     406This parameter is position-free and uses a backtick routine resize (`resize). It represents the old dynamic object (oaddr) that the programmer wants to
     407\begin{itemize}
     408\item
     409resize to a new size.
     410\item
     411realign to a new alignment
     412\item
     413fill with something.
     414\end{itemize}
     415The data in old dynamic object will not be preserved in the new object. The type of object passed to `resize and the returned type of alloc call can be different.
     416
     417Example: int b = alloc( 5 , a`resize )
     418This call will resize object a to a dynamic array that can contain 5 integers.
     419
     420Example: int b = alloc( 5 , a`resize , 32`align )
     421This call will resize object a to a dynamic array that can contain 5 integers. The returned object will also be aligned to 32.
     422
     423Example: int b = alloc( 5 , a`resize , 32`align , 2`fill)
     424This call will resize object a to a dynamic array that can contain 5 integers. The returned object will also be aligned to 32 and will be filled with 2.
     425
     426\paragraph{Realloc}
     427This parameter is position-free and uses a backtick routine realloc (`realloc). It represents the old dynamic object (oaddr) that the programmer wants to
     428\begin{itemize}
     429\item
     430realloc to a new size.
     431\item
     432realign to a new alignment
     433\item
     434fill with something.
     435\end{itemize}
     436The data in old dynamic object will be preserved in the new object. The type of object passed to `realloc and the returned type of alloc call cannot be different.
     437
     438Example: int b = alloc( 5 , a`realloc )
     439This call will realloc object a to a dynamic array that can contain 5 integers.
     440
     441Example: int b = alloc( 5 , a`realloc , 32`align )
     442This call will realloc object a to a dynamic array that can contain 5 integers. The returned object will also be aligned to 32.
     443
     444Example: int b = alloc( 5 , a`realloc , 32`align , 2`fill)
     445This call will resize object a to a dynamic array that can contain 5 integers. The returned object will also be aligned to 32. The extra space after copying data of a to the returned object will be filled with 2.

  • doc/theses/mubeen_zulfiqar_MMath/benchmarks.tex

    rc86ee4c rd83b266  
    149149*** FIX ME: Insert a figure of above benchmark with description
    150150
    151 \subsubsection{Relevant Knobs}
     151\paragrpah{Relevant Knobs}
    152152*** FIX ME: Insert Relevant Knobs
    153153
    … …  
    202202\paragraph{Relevant Knobs}
    203203*** FIX ME: Insert Relevant Knobs
    204 
    205 \section{Results}
    206 *** FIX ME: add configuration details of memory allocators
    207 
    208 \subsection{Memory Benchmark}
    209 
    210 \subsubsection{Relevant Knobs}
    211 
    212 \subsection{Speed Benchmark}
    213 
    214 \subsubsection{Speed Time}
    215 
    216 \paragraph{Relevant Knobs}
    217 
    218 \subsubsection{Speed Workload}
    219 
    220 \paragraph{Relevant Knobs}
    221 
    222 \subsection{Cache Scratch}
    223 
    224 \subsubsection{Cache Scratch Time}
    225 
    226 \paragraph{Relevant Knobs}
    227 
    228 \subsubsection{Cache Scratch Layout}
    229 
    230 \paragraph{Relevant Knobs}
    231 
    232 \subsection{Cache Thrash}
    233 
    234 \subsubsection{Cache Thrash Time}
    235 
    236 \paragraph{Relevant Knobs}
    237 
    238 \subsubsection{Cache Thrash Layout}
    239 
    240 \paragraph{Relevant Knobs}

  • doc/theses/mubeen_zulfiqar_MMath/performance.tex

    rc86ee4c rd83b266  
    11\chapter{Performance}
     2
     3\noindent
     4====================
     5
     6Writing Points:
     7\begin{itemize}
     8\item
     9Machine Specification
     10\item
     11Allocators and their details
     12\item
     13Benchmarks and their details
     14\item
     15Results
     16\end{itemize}
     17
     18\noindent
     19====================
     20
     21\section{Memory Allocators}
     22For these experiments, we used 7 memory allocators excluding our standalone memory allocator uHeapLmmm.
     23
     24\begin{tabularx}{0.8\textwidth} {
     25        | >{\raggedright\arraybackslash}X
     26        | >{\centering\arraybackslash}X
     27        | >{\raggedleft\arraybackslash}X |
     28}
     29\hline
     30Memory Allocator & Version     & Configurations \\
     31\hline
     32dl               &             &  \\
     33\hline
     34hoard            &             &  \\
     35\hline
     36je               &             &  \\
     37\hline
     38pt3              &             &  \\
     39\hline
     40rp               &             &  \\
     41\hline
     42tbb              &             &  \\
     43\hline
     44tc               &             &  \\
     45\end{tabularx}
     46(FIX ME: complete table)
     47
     48\section{Experiment Environment}
     49We conducted these experiments ... (FIX ME: what machine and which specifications to add).
     50
     51We used our micro becnhmark suite (FIX ME: cite mbench) to evaluate other memory allocators (FIX ME: cite above memory allocators) and our uHeapLmmm.
     52
     53\section{Results}
     54
     55\subsection{Memory Benchmark}
     56FIX ME: add experiment, knobs, graphs, and description
     57
     58\subsection{Speed Benchmark}
     59FIX ME: add experiment, knobs, graphs, and description
     60
     61\subsubsection{Speed Time}
     62FIX ME: add experiment, knobs, graphs, and description
     63
     64\subsubsection{Speed Workload}
     65FIX ME: add experiment, knobs, graphs, and description
     66
     67\subsection{Cache Scratch}
     68FIX ME: add experiment, knobs, graphs, and description
     69
     70\subsubsection{Cache Scratch Time}
     71FIX ME: add experiment, knobs, graphs, and description
     72
     73\subsubsection{Cache Scratch Layout}
     74FIX ME: add experiment, knobs, graphs, and description
     75
     76\subsection{Cache Thrash}
     77FIX ME: add experiment, knobs, graphs, and description
     78
     79\subsubsection{Cache Thrash Time}
     80FIX ME: add experiment, knobs, graphs, and description
     81
     82\subsubsection{Cache Thrash Layout}
     83FIX ME: add experiment, knobs, graphs, and description
Note: See TracChangeset for help on using the changeset viewer.