[gnuastro-commits] master 45d4e2a3: Makefile extensions: new function to batch by available RAM

[Mohammad Akhlaghi]

branch: master
commit 45d4e2a3faa3db6188ebdc9a99bdc1a7a9ab5e11
Author: Mohammad Akhlaghi <mohammad@akhlaghi.org>
Commit: Mohammad Akhlaghi <mohammad@akhlaghi.org>

    Makefile extensions: new function to batch by available RAM
    
    Until now, in the Makefile we only had 'makeplugin_text_prev_batch_in_list'
    function which required you to manually insert the number of files in each
    batch. But when we go from one system to another, depending on the
    available RAM and number of threads, that number needs to be changed. This
    would make the pipeline non-automatic, which is very bad and potentially
    causes many bugs.
    
    Furthermore the underlying algorithm that was used to divide the input
    files into batches was not very optimal (would parse the full list for
    every target, do many extra allocations and etc).
    
    With this commit, a new function has been added that will read the
    avialable RAM in the operating system and take the amount of RAM needed by
    each instance of the recipe to automatically find the number of elements in
    each batch.
    
    Furthermore, a new algorithm is now used to divide the input files into
    batches: when Make is run in parallel on many files, this is much faster
    (by almost 50% for 12 threads) than the previous algorithm. The new
    function is now also used in the 'makeplugin_text_prev_batch_in_list'
    (which has now lost the redundant '_in_list' suffix to make it easier to
    use).
---
 NEWS              |  28 +++++---
 doc/gnuastro.texi |  89 +++++++++++++++++++++++--
 lib/makeplugin.c  | 195 ++++++++++++++++++++++++++++++++++++++++++------------
 3 files changed, 254 insertions(+), 58 deletions(-)

diff --git a/NEWS b/NEWS
index cb0aa805..de9f813f 100644
--- a/NEWS
+++ b/NEWS
@@ -43,15 +43,25 @@ See the end of the file for license conditions.
     Infante-Sainz.
 
 *** Makefile extensions
-  - $(ast-text-prev-in-list TARGET, LIST): select the word that is previous
-    to 'TARGET' in a list of words. See the documentation for a fully
-    working example and how this can be useful.
-
-  - $(ast-text-prev-batch-in-list TARGET, NUM, LIST): select the previous
-    "batch" of 'NUM' words (in relation to the batch that contains
-    'TARGET'). This is useful for steps in your pipelines were you need to
-    limit the parallelization to batches. See the example in the book for a
-    fully working example.
+  - $(ast-text-prev TARGET, LIST): select the word that is previous to
+    'TARGET' in a list of words. See the documentation for a fully working
+    example and how this can be useful.
+
+  - $(ast-text-prev-batch TARGET, NUM, LIST): select the previous "batch"
+    of 'NUM' words (in relation to the batch that contains 'TARGET'). This
+    is useful for steps in your pipelines were you need to limit the
+    parallelization to batches. See the example in the book for a fully
+    working example.
+
+  - $(ast-text-prev-batch-by-ram TARGET, NEEDED_RAM_GB, LIST): select the
+    previous batch of words in 'LIST' such that the total consumed RAM by
+    all the parallel executions does not exceed the available RAM when Make
+    starts. The 'NEEDED_RAM_GB' variable is the amount of RAM that is
+    needed to create one target (in Gigabytes). Like 'ast-text-prev-batch',
+    this is useful for steps in a pipeline that require a large amount of
+    RAM (thus not allowing parallel execution), but this is more generic
+    and adapts to different systems with very different RAM and/or CPU
+    threads.
 
 ** Removed features
 ** Changed features
diff --git a/doc/gnuastro.texi b/doc/gnuastro.texi
index 5f95a867..fbc79a3a 100644
--- a/doc/gnuastro.texi
+++ b/doc/gnuastro.texi
@@ -35968,7 +35968,7 @@ all:
      echo $(ast-text-not-contains Aa, $(list))
 @end example
 
-@item $(ast-text-prev-in-list TARGET, LIST)
+@item $(ast-text-prev TARGET, LIST)
 Returns the word in @code{LIST} that is previous to @code{TARGET}.
 If @code{TARGET} is the first word of the list, or is not within it at all, 
this function will return an empty string (nothing).
 
@@ -36002,7 +36002,7 @@ subsubs := $(foreach s, $(subids), \
                $(s)-$(ss).fits))
 
 # Build the sub-components:
-$(subsubs): %.fits: $$(ast-text-prev-in-list \
+$(subsubs): %.fits: $$(ast-text-prev \
                        $$(word 1, $$(subst -, ,%)).fits, \
                        $(subs))
         @@echo "$@@: $^"
@@ -36021,14 +36021,15 @@ Without this function, make first builds all the 
sub-sub-components, then goes t
 There can be any level of components between these, allowing this operation to 
be as complex as necessary in your data analysis pipeline.
 Unfortunately the @code{.NOTPARALLEL} target of GNU Make doesn't allow this 
level of customization.
 
-@item $(ast-text-prev-batch-in-list TARGET, NUM, LIST)
+@item $(ast-text-prev-batch TARGET, NUM, LIST)
 Returns the previous batch of @code{NUM} words in @code{LIST} (in relation to 
the batch containing @code{TARGET}).
-In the special case that @code{NUM=1}, this is equivalent to the 
@code{ast-text-prev-in-list} function that is described above.
+In the special case that @code{NUM=1}, this is equivalent to the 
@code{ast-text-prev} function that is described above.
 
 Here is one scenario where this function is useful: in astronomy datasets are 
can easily be very large.
 Therefore, some Make recipes in your pipeline may require a lot of memory; 
such that executing them on all the available threads (for example 12 threads 
with @code{-j12}) will immediately occupy all your RAM, causing a crash in your 
pipeline.
 However, let's assume that you have sufficient RAM to execute 4 targets of 
those recipes in parallel.
 Therefore while you want all the other steps of your pipeline to be using all 
12 threads, you want one rule to only build 4 targets at any time.
+But before starting to use this function, also see 
@code{ast-text-prev-batch-by-ram}.
 
 The example below demonstrates the usage of this function in a minimal working 
example of the scenario above: we want to build 15 targets, but in batches of 4 
target at a time, irrespective of how many threads Make was executed with.
 
@@ -36041,12 +36042,12 @@ targets := $(foreach i,$(shell seq 15),a-$(i).fits)
 
 all: $(targets)
 
-$(targets): $$(ast-text-prev-batch-in-list $$@@,4,$(targets))
-     @@echo "$@@: $^"
+$(targets): $$(ast-text-prev-batch $$@@,4,$(targets))
+        @@echo "$@@: $^"
 @end example
 
 @noindent
-If you place the example above in a plain-text file called @file{Makefile} 
(correcting for the TAB at the start of the recipe), and run Make on 12 
threads, you will see an output like below.
+If you place the example above in a plain-text file called @file{Makefile} 
(correcting for the TAB at the start of the recipe), and run Make on 12 threads 
like below, you will see the following output.
 The targets in each batch are not ordered (and the order may change in 
different runs) because they have been run in parallel.
 
 @example
@@ -36068,6 +36069,80 @@ a-15.fits: a-9.fits a-10.fits a-11.fits a-12.fits
 a-14.fits: a-9.fits a-10.fits a-11.fits a-12.fits
 @end example
 
+Any other rule that is later added to this make file (as a prerequisite/parent 
of @code{targets} or as a child of @code{targets}) will be run on 12 threads.
+
+@item $(ast-text-prev-batch-by-ram TARGET, NEEDED_RAM_GB, LIST)
+@cindex RAM
+Similar to @code{ast-text-prev-batch}, but instead of taking the number of 
words/files in each batch, this function takes the maximum amount of RAM that 
is needed by one instance of the recipe.
+Through the @code{NEEDED_RAM_GB} argument, you should specify the amount of 
ram that a @emph{single} instance of the recipe in this rule needs.
+The number of files in each batch is then calculated internally by reading the 
available RAM on the system.
+Therefore this function is more generalizable to different computers (with 
very different RAM and/or CPU threads).
+
+For example, assume evey instance of one rule in your Makefile requires a 
maximum of 5.2 GB of RAM during its execution, and your computer has 32 GB of 
RAM and 2 threads.
+In this case, you do not need to manage the targets at all: at the worst 
moment your pipeline will consume 10.4GB of RAM (much smaller than the 32GB of 
RAM that you have).
+However, you later run the same pipeline on another machine with identical 
RAM, but 12 threads!
+In this case, you will need @mymath{5.2\times12=62.4}GB of RAM; but the new 
system doesn't have that much RAM, causing your pipeline to crash.
+If you used @code{ast-text-prev-batch} function (described above) to manage 
these hardware limitations, you would have to manually change the number on 
every new system; this is inconvenient, can cause many bugs, and requires 
manual intervention (not making your pipeline automatic).
+
+The @code{ast-text-prev-batch-by-ram} function was designed as a solution to 
the problem above: it will read the amount of available RAM at the time that 
Make starts (before the recipes in your pipeline are actually executed).
+From the value to @code{NEEDED_RAM_GB}, it will then estimate how many 
instances of that recipe can be executed in parallel without breaching the 
available RAM of the system.
+Therefore it is important to not run another heavy RAM consumer on the system 
while your pipeline is being executed.
+Note that this function reads the available RAM, not total RAM; it therefore 
accounts for the background operations of the operating system or graphic user 
environment that are running in parallel to your pipeline; and assumes they 
will remain at the same level.
+
+The fully working example below shows the usage of this function in a scenario 
where we assume the recipe requires 4.2GB of RAM for each target.
+
+@example
+load /usr/local/lib/libgnuastro_make.so
+
+.SECONDEXPANSION:
+
+targets := $(foreach i,$(shell seq 13),$(i).fits)
+
+all: $(targets)
+
+$(targets): $$(ast-text-prev-batch-by-ram $$@@,4.2,$(targets))
+        @@echo "$@@: $^"
+@end example
+
+@noindent
+Once the contents above are placed in a @file{Makefile} and you execute the 
command below in a system with about 27GB of available RAM (total RAM is 32GB; 
the 5GB difference is used by the operating system and other background 
programs), you will get an output like below.
+
+@example
+$ make -j12
+1.fits:
+2.fits:
+3.fits:
+4.fits:
+5.fits:
+6.fits:
+7.fits: 1.fits 2.fits 3.fits 4.fits 5.fits 6.fits
+8.fits: 1.fits 2.fits 3.fits 4.fits 5.fits 6.fits
+11.fits: 1.fits 2.fits 3.fits 4.fits 5.fits 6.fits
+10.fits: 1.fits 2.fits 3.fits 4.fits 5.fits 6.fits
+9.fits: 1.fits 2.fits 3.fits 4.fits 5.fits 6.fits
+12.fits: 1.fits 2.fits 3.fits 4.fits 5.fits 6.fits
+13.fits: 7.fits 8.fits 9.fits 10.fits 11.fits 12.fits
+@end example
+
+Depending on the amount of available RAM on your system, you will get a 
different output.
+To see the effect, you can decrease or increase the amount of required RAM 
(@code{4.2} in the example above).
+
+
+@cartouche
+@noindent
+@cindex RAM usage (maximum)
+@strong{What is the maximum RAM required by my command?} Put a 
`@code{/usr/bin/time --format=%M}' prefix behind your full command (including 
any options and arguments).
+For example like this for a call to Gnuastro's Warp program:
+
+@example
+/usr/bin/time --format=%M astwarp image.fits
+@end example
+
+After the regular outputs of the program, you will see a number on the last 
line.
+This number is the maximum used RAM (in @emph{kilobytes}) during the execution 
of the program.
+Later, you can convert this to Gigabytes (to feed into this function) by 
dividing it to @mymath{10^6}.
+@end cartouche
+
 @end table
 
 
diff --git a/lib/makeplugin.c b/lib/makeplugin.c
index 8967eb3d..57daeeb5 100644
--- a/lib/makeplugin.c
+++ b/lib/makeplugin.c
@@ -31,6 +31,7 @@ along with Gnuastro. If not, see 
<http://www.gnu.org/licenses/>.
 #include <gnumake.h>
 
 #include <gnuastro/txt.h>
+#include <gnuastro/pointer.h>
 
 #include <gnuastro-internal/options.h>
 #include <gnuastro-internal/checkset.h>
@@ -48,13 +49,15 @@ int plugin_is_GPL_compatible=1;
 
 /* Names of the separate functions. */
 #define MAKEPLUGIN_FUNC_PREFIX "ast"
+
 /* Basic text functions */
+static char *text_prev=MAKEPLUGIN_FUNC_PREFIX"-text-prev";
 static char *text_to_upper=MAKEPLUGIN_FUNC_PREFIX"-text-to-upper";
 static char *text_to_lower=MAKEPLUGIN_FUNC_PREFIX"-text-to-lower";
+static char *text_prev_batch=MAKEPLUGIN_FUNC_PREFIX"-text-prev-batch";
+static char 
*text_prev_batch_by_ram=MAKEPLUGIN_FUNC_PREFIX"-text-prev-batch-by-ram";
 static char *text_contains_name=MAKEPLUGIN_FUNC_PREFIX"-text-contains";
-static char *text_prev_in_list=MAKEPLUGIN_FUNC_PREFIX"-text-prev-in-list";
 static char *text_not_contains_name=MAKEPLUGIN_FUNC_PREFIX"-text-not-contains";
-static char 
*text_prev_batch_in_list=MAKEPLUGIN_FUNC_PREFIX"-text-prev-batch-in-list";
 
 /* Gnuastro analysis functions */
 static char *version_is_name=MAKEPLUGIN_FUNC_PREFIX"-version-is";
@@ -207,8 +210,7 @@ makeplugin_text_to_lower(const char *caller, unsigned int 
argc,
 
 /* Return the previous word in the given list. */
 static char *
-makeplugin_text_prev_in_list(const char *caller, unsigned int argc,
-                             char **argv)
+makeplugin_text_prev(const char *caller, unsigned int argc, char **argv)
 {
   int found=0;
   char *prev=NULL, *target=argv[0];
@@ -229,15 +231,107 @@ makeplugin_text_prev_in_list(const char *caller, 
unsigned int argc,
 
 
 
+/* Given one of the words of the input list, this function will return a
+   string containing the previous batch of words. */
+static char *
+makeplugin_text_prev_batch_work(char *target, size_t num_in_batch,
+                                char *list)
+{
+  int is_first_batch=1;
+  size_t anum=0, starti, endi, outlen;
+  char *startend[4]={NULL, NULL, NULL, NULL};
+  char *cp, *token, *saveptr=NULL, *out=NULL, *delimiters=" ";
+
+  /* Parse the line to find the desired element, but first copy the input
+     list into a new editable space with 'strdupa'. */
+  gal_checkset_allocate_copy(list, &cp);
+  token=strtok_r(cp, delimiters, &saveptr);
+  do
+    {
+      /* For the first num_in_batch elements, we don't should not set the
+         first two pointers of 'startend'. Startend contains the following
+         four pointers:
+
+           startend[0] --> FIRST token in PREVIOUS batch.
+           startend[1] --> LAST  token in PREVIOUS batch.
+           startend[2] --> FIRST token in THIS     batch.
+           startend[3] --> LAST  token in THIS     batch.
+
+         First, let's check if we at the start of a batch: if so, all the
+         elements of 'startend' need to be reset. */
+      if(anum % num_in_batch==0)
+        {
+          /* Only for the non-first batches: move the start/end to the
+             "PREVIOUS" batch and remove the ending of current batch. */
+          if(is_first_batch==0)
+            {
+              startend[0]=startend[2];
+              startend[1]=startend[3];
+            }
+
+          /* Put this token at the start of this batch and set the end of
+             this batch to be NULL. */
+          startend[3]=NULL;
+          startend[2]=token;
+        }
+
+      /* This is the last element of this batch, write startend[3] and
+         remove the 'isfirstbatch' flag. */
+      if(anum % num_in_batch == num_in_batch-1)
+        { startend[3]=token; is_first_batch=0; }
+
+      /* For a check:
+      printf("%zu: %s (%zu of %zu)\n"
+             "     %s\n     %s\n     %s\n     %s\n\n", anum,
+             token, (anum%num_in_batch)+1, num_in_batch, startend[0],
+             startend[1], startend[2], startend[3]);
+      */
+
+      /* If the target is reached, break out of the loop. */
+      if( !strcmp(target, token) ) break;
+
+      /* Go to the next token. */
+      ++anum; /* Count of all tokens. */
+      token=strtok_r(NULL, delimiters, &saveptr);
+    }
+  while(token);
+
+  /* We need to return a non-empty output only when a previous batch
+     exists.*/
+  if(startend[0])
+    {
+      /* Find the positions of the start and end of the output string
+         within the (copied) input string and from that measure the length
+         of the output string. */
+      starti=startend[0]-cp;
+      endi=startend[1]+strlen(startend[1])-cp;
+      outlen=endi-starti;
+
+      /* Allocate the output and copy the input into it. */
+      out=gal_pointer_allocate(GAL_TYPE_STRING, outlen+1, 0, __func__,
+                               "out");
+      memcpy(out, &list[starti], outlen);
+      out[outlen]='\0';
+    }
+  else out=NULL;
+
+  /* Clean up and return. */
+  free(cp);
+  return out;
+}
+
+
+
+
+
 /* Return the previous word in the given list. */
 static char *
-makeplugin_text_prev_batch_in_list(const char *caller, unsigned int argc,
-                                   char **argv)
+makeplugin_text_prev_batch(const char *caller, unsigned int argc,
+                           char **argv)
 {
+  size_t num;
   void *nptr;
-  char *out, *target=argv[0];
-  size_t i=0, num, batch, start;
-  gal_list_str_t *tmp, *olist=NULL, *list=gal_list_str_extract(argv[2]);
+  char *target=argv[0], *list=argv[2];
 
   /* Interpret the number. */
   nptr=&num;
@@ -245,36 +339,49 @@ makeplugin_text_prev_batch_in_list(const char *caller, 
unsigned int argc,
     error(EXIT_SUCCESS, 0, "'%s' could not be read as an "
           "unsigned integer", argv[1]);
 
-  /* Parse the input list. */
-  for(tmp=list; tmp!=NULL; tmp=tmp->next)
-    { if( !strcmp(tmp->v,target) ) { break; } ++i; }
-
-  /* Set the starting counter for the batch strings to return. f we are in
-     the first batch, or if the given string isn't in the list at all, we
-     don't want to retun anything. */
-  batch=i/num;
-  if(batch==0 || tmp==NULL) return NULL;
-  else
-    {
-      /* We want to return the previous batch, so we'll decrement the
-         batch, and calculate the starting index from that. */
-      start = --batch*num;
+  /* Generate the outputs.*/
+  return makeplugin_text_prev_batch_work(target, num, list);
+}
 
-      /* Add the strings to the output string. */
-      i=0;
-      for(tmp=list; tmp!=NULL; tmp=tmp->next)
-        {
-          if(i>=start && i<start+num) gal_list_str_add(&olist, tmp->v, 0);
-          ++i;
-        }
-    }
 
-  /* Build the output pointer, clean up and return. */
-  gal_list_str_reverse(&olist);
-  out=gal_list_str_cat(olist, ' ');
-  gal_list_str_free(list,  1);  /* This is the original list.     */
-  gal_list_str_free(olist, 0);  /* We didn't allocate new copies. */
-  return out;
+
+
+
+/* Return the previous elements in the list based on the available RAM and
+   the amount of RAM each invocation needs (in Gigabytes of normal decimal
+   1000s base, not 1024s). To get the amount of RAM of each invocation, you
+   can use the command below (which will return the maximum necessary RAM
+   in Kilobytes).
+
+   /usr/bin/time --format=%M command ....
+
+   To convert this to Gigabytes, you can use this command (just replace the
+   number):
+
+   echo "2374764" | awk '{print $1*1e3/1e9}'
+
+   Afterwards, try to round it upwards (so some RAM is always left for the
+   OS).
+*/
+static char *
+makeplugin_text_prev_batch_by_ram(const char *caller, unsigned int argc,
+                                  char **argv)
+{
+  void *nptr;
+  float needed_gb;
+  char *target=argv[0], *list=argv[2];
+  size_t num, ram_b=gal_checkset_ram_available(1);
+
+  /* Interpret the number. */
+  nptr=&needed_gb;
+  if( gal_type_from_string(&nptr, argv[1], GAL_TYPE_FLOAT32) )
+    error(EXIT_SUCCESS, 0, "'%s' could not be read as an "
+          "unsigned integer", argv[1]);
+
+  /* Estimate the number of words in each batch (to be run in parallel if
+     this function is used in targets list) and call the final function. */
+  num=(size_t)(ram_b/(needed_gb*1e9));
+  return makeplugin_text_prev_batch_work(target, num, list);
 }
 
 
@@ -442,12 +549,16 @@ libgnuastro_make_gmk_setup()
                    1, 1, GMK_FUNC_DEFAULT);
 
   /* Select previous item in list*/
-  gmk_add_function(text_prev_in_list, makeplugin_text_prev_in_list,
-                   2, 2, GMK_FUNC_DEFAULT);
+  gmk_add_function(text_prev, makeplugin_text_prev, 2, 2,
+                   GMK_FUNC_DEFAULT);
+
+  /* Select batch of previous 'num' elements in list. */
+  gmk_add_function(text_prev_batch, makeplugin_text_prev_batch,
+                   3, 3, GMK_FUNC_DEFAULT);
 
-  /* Select batch of previous 'num' elements in list.*/
-  gmk_add_function(text_prev_batch_in_list,
-                   makeplugin_text_prev_batch_in_list,
+  /* Select batch  */
+  gmk_add_function(text_prev_batch_by_ram,
+                   makeplugin_text_prev_batch_by_ram,
                    3, 3, GMK_FUNC_DEFAULT);