From b4e8a41aca5a22fc02da3b1a29ca10e4d472b6c7 Mon Sep 17 00:00:00 2001 From: Bent Bisballe Nyeng Date: Fri, 4 Aug 2023 21:30:35 +0200 Subject: A6: WIP --- a6/au_BentBisballeNyeng_A6.tex | 154 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 154 insertions(+) create mode 100644 a6/au_BentBisballeNyeng_A6.tex (limited to 'a6/au_BentBisballeNyeng_A6.tex') diff --git a/a6/au_BentBisballeNyeng_A6.tex b/a6/au_BentBisballeNyeng_A6.tex new file mode 100644 index 0000000..ad4cc0d --- /dev/null +++ b/a6/au_BentBisballeNyeng_A6.tex @@ -0,0 +1,154 @@ +\title{Essay: Applying Contemporary C++ in Enviroments Without +Free-Store} +\documentclass[11pt]{article} +\usepackage{graphicx} +%\usepackage{xcolor} +\usepackage{fancyhdr} +\usepackage{listings} +\usepackage{subfig} +\usepackage{biblatex} +\addbibresource{references.bib} +\renewcommand{\floatpagefraction}{.8}% +%\renewcommand{\thesubfigure}{Figure \arabic{subfigure}} +\captionsetup[subfigure]{labelformat=simple, labelsep=colon} +\pagestyle{fancy} +\author{Bent Bisballe Nyeng University of Aarhus} +\begin{document} +\maketitle + +\begin{abstract} +%\section*{Abstract} + +In this essay I want to examine to which extend it is possible to use +free-store allocating constructs from the standard template library +(STL) and C++ core-language in enviroments without access to a +free-store. +\end{abstract} + +\section{Introduction} +C++ contains a lot of helpful constructs that can be widely used, +including in environments without a free-store, such +as \texttt{concepts}, \texttt{module}s, \texttt{template}s in general, +and functions from \texttt{algorithm} in particular but some parts of +the language and the STL is off-limits when building applications in +environments without free-store such as the perhaps obvious, but +useful \texttt{std::vector} or \texttt{std::string}, but also the less +obvious co-routines\cite{belson} or storing lambdas +in \texttt{std::function}s\cite{elbeno}. +This also inherently means that RAII cannot be used for managing memory +allocations (such as smart-pointers), but can still be used for +managing other types of resources, such as locks or hardware +peripheral access. + +\subsection{Dynamic Memory Allocation} + +There can be many reasons for not allocating on the free-store, either +by convention; ``no allocations allowed after the engines has +started'', or because the hardware or operating system doesn't +have a virtual memory abstraction, ie. doesn't have a memory +management unit (MMU)\cite{tannenbaum}, and therefore, over time, is +at risk at fragmenting the memory available ultimately leading to +memory depletion\cite{weis}. + +In the case of memory fragmentation one might argue that it is not the +allocation that is the problem but rather the free'ing since this is +when the fragmentation happens. This problem is shown in +figure \ref{frag}, which might be possible to circumvent in singular +concrete cases, but cannot be solved in general without the page +indirections of the virtual memory\cite{weis}. + +\begin{figure} +\makebox[\textwidth][c]{% +\includegraphics[scale=0.8]{fragmentation.pdf}} +\caption{\textit{(a) visualizes the full, free, memory of a system. +Then, in (b), 4 equal-sized chunks of memory has been allocated +filling up the whole memory. In (c) chunk 2 and 4 has been free'd and +finally, in (d), a chunk which can fit in the total amount of +free memory, is being allocated but fails because of memory +fragmentation.}} +\label{frag} +\end{figure} + +This can to some degree be prevented by monotonic allocations which +might work for not very practical in real-world +software and certainly not for the dynamic allocations in the STL or +the core-language. + +In particular, a lambda stored in a \texttt{std::function} might +allocate memory on the free-store if the lambda exceeds the size of +the (compiler dependent) small-buffer optimization (SBO) buffer inside +the \texttt{std::functions}\cite{elbeno}. In much the same way as +the \texttt{std::string} has its small string optimization (also +compiler dependent). + +\subsection{Free-Standing} + +Work is being done to modify the ``free-standing C++'' towards, among +other things, making it run on systems without free-store by isolating +the parts of the STL that can be used entirely without allocating +along with not supporting exceptions and run-time type +information\cite{craig}. + +Working with the resulting small sub-set of the available components, +however, is not well suited for making contemporary C++ applications. +The ideal solution would be to find ways to be able to use all (or at +least most) features, but with a potential known set of restictions or +limitations. + +\section{Method} +In the following, 3 methods for managing memory allocations will be +investigated, and their suitability for real-life applications be +evaluated: +\begin{itemize} +\item Using Custom Allocators for the STL components that supports it. +\item Overloading \texttt{new}/\texttt{delete} to use stack allocated + memory instead of the free-store for all allocation. +\item Support from the compiler to fail compilation if an + unintentional \texttt{new} or \texttt{delete} is being called, + at least preventing accidental allocations. +\end{itemize} + +Each of the three will be evaluated with large lambda +captures, \texttt{std::vector} allocation and some simple co-routines. +The epxeriments are done on a linux PC using the gcc-11.2 compiler. + +\section{Experiments} + + +---------------------------------------- + + +No access to MMU, implicitly, prohibits calls to delete after +initialization phase. Otherwise this will lead to memory fragmentation +which again might lead to free-store depletion and ultimately +application failure. + +Writing a custom allocator is only a solution to a sub-set of the +allocations in an application, for example if all allocations are +guaranteed to always be of the same size, in which can no +fragmentation will occur. + +But for most applications (or at least most parts on an application) +this is not the case, and therefore others means need to be taken into +use. + +The most common way of addressing this, is simply to only use stack +allocation, or store all objects in as static globals. +But in certain areas of the C++ language dynamic allocation might +occur without the developer knowing about it. +\texttt{std::string}s of sizes that doesn't fit in the SSO buffer is +one example, but even more devious is the capture clause of a +lambda, which might allocate extra memory, if more than $N$ members +are captured, where $N$ is compiler dependent. + +No way of telling the compiler that ``no allocations allowed, fail if +one is made'' exists, but one could wish for such a mechanism in the +wake of the ``free-standing C++'' subset work. +One thing is to prohibit use of language constructs that are +guaranteed to allocate, but quite another is to allow using constructs +in ways that doesn't make them allocate. +This, I think, is not part of the ``free-standing C++'' work. + +\printbibliography + +\end{document} -- cgit v1.2.3