Software Development : Structured Programming

From bitrary
Jump to: navigation, search

Software Development : ABC


As the Internet is full of introductory material, this section will contain only a few remarks that might give the material at other sites a bit different flavor.


Loops

Translatability

Any common loop construct can be rewritten by using any other common loop construct. For example, the following for-loop

for(i=0;i<42;i++){
    do_something();
} // for

is equivalent to the following while-loop:

i=0;
while (i<42){
    do_something();
    i++;
}

which is equivalent to the following (Ruby) code:

i=0
begin
    if (i<42)
        do_something();
        i++;
    end # if
end while (i<42)

which in turn can be rewritten as the for-loop at the start of this example.


Generalisations

By citing Андрей Николаевич Терехов, a way to comprehensibly describe a loop is:

FOR i FROM a BY b TO c WHILE d 
    DO f OD


Loop Parallelization

If separate iterations of a loop do not depend on each other, then the result of the loop does not depend on the execution order of its iterations.


        function the_output_of_this_function_does_not_depend_on_the_rand_value(x) {
            var ar_data = [42, 77, 55];
            // 0.0 <= Math.random() <= 1.0
            var b_choice_1 = (0.5 <= Math.random());
            if (b_choice_1) {
                for (i = 0; i < 3; i++) {
                    ar_data[i] = ar_data[i] + x;
                } // for
            } else {
                if (0.5 <= Math.random()) {
                    // The key phrase here is: "loop unrolling".
                    // If loops are short "enough", then the
                    // unrolling can be used as an assembler
                    // level optimization technique that is based
                    // on the idea that by unrolling a loop, there is
                    // no need to allocate a CPU register for
                    // the loop iteration variable, in this case,
                    // "the i", and the "i=0" assembler command
                    // can also be skipped.
                    ar_data[1] = ar_data[1] + x;
                    ar_data[2] = ar_data[2] + x;
                    ar_data[0] = ar_data[0] + x;
                } else {
                    if (0.5 <= Math.random()) {
                        ar_data[2] = ar_data[2] + x;
                        ar_data[1] = ar_data[1] + x;
                        ar_data[0] = ar_data[0] + x;
                    } else {
                        ar_data[1] = ar_data[1] + x;
                        ar_data[0] = ar_data[0] + x;
                        ar_data[2] = ar_data[2] + x;
                    } // else
                } // else
            } // else
            return ar_data;
        } // the_output_of_this_function_does_not_depend_on_the_rand_value


Loop parallelization that takes advantage of the CPU SIMD(Single-Instruction-Multiple-Data) instructions is called vectorization. As of 2015 the command line arguments for switching in vectorization of GCC and LLVM is:

S_THE_REST=" -ftree-vectorize "
-mtune=native $S_THE_REST # optimizes for the current CPU, but inserts extra code 
                          # for backwards compatibility with older CPU types

-march=native $S_THE_REST # optimizes for the current CPU, but 
                          # does NOT insert the extra code for the 
                          # backwards compatibility with the older CPU types


Loop parallelization can be used for executing different iterations of the loop at different computers in a cluster. In that case program execution continues after the results of all of the iterations of the loop have been received from the various computers in the cluster. The keyword is MapReduce. If in stead of a cluster the iterations are run at different CPU cores of a single computer, then one possible algorithm for spreading the iterations between CPU cores is to load the iteration tasks to a queue and have the CPU cores fetch the tasks from that queue at their own pace. More detailed descriptions of that algorithm can be found by searching the phrase "work stealing", but a key thing to remember with that algorithm is that the activity of distributing the tasks between CPU cores can be too expensive for some tasks and to start an operating system process is even more expensive.


The Amdahl’s law

Speed-up that can be achieved by algorithm parallelization has a theoretical limit that can be explained by an example, where the algorithm consists of 3 function calls.

        function the_algorithm() {
            func_part_1(); //if sequential, takes 0.2 time units
            func_part_2(); //if sequential, takes 0.5 time units
            func_part_3(); //if sequential, takes 0.3 time units
            // 0.2 + 0.5 + 0.3 = 1.0
        } // the_algorithm

If the time spent on the execution of the func_part_2() were divided by 2 by parallelizing the func_part_2() and executing the iterations on 2 CPU cores in parallel, then the whole execution time of the func_part_2() would be

$$\cfrac{0.5 timeunits}{2} = 0.25 timeunits$$

and the time spent on the execution of the_algorithm() would be

$$0.2 timeunits + 0.25 timeunits + 0.3 timeunits = 0.75 timeunits$$

If the func_part_1() were to be executed on 100 CPU-cores in parallel and the func_part_2() and func_part_3() were executed on a single CPU core, then the time spent on the execution of the_algorithm() would still be

$$\cfrac{0.2 timeunits}{100} + 0.5 timeunits + 0.3 timeunits = 0.002 timeunits + 0.8 timeunits = 0.802 timeunits$$


INCOMPLETE, POOLELI, lisada profileerimise peatükk, sinna teadusarvutuste graafi-lõikamise algoritm ning siis interpreteeritavate keelte JIT'i sisseülituse vältimisest tulenev muutujate väljaspool tsüklit deklareerimise jutt. Profileerimise peatükki lisada ka GCC ja LLVM'iga binaaride instrumenteerimise osa.


References

Multithreaded Programming Related References


Recursion

A recursive function is a function that has at least one call to itself as part of its implementation. A tail-recursive function is a function that contains exactly one call to itself and that call to itself resides at the very last line before return statement. Any tail-recursive function can be re-written as a while-loop.

        function a_tailrecursive_function(a, b) {
            if (20 <= a) { // Recursion stop condition.
                return a;
            } // if
            var a_new = a + b;
            var c = a_tailrecursive_function(a_new, b);
            return c;
        } // a_tailrecursive_function

        function the_tailrecursive_function_converted_to_a_loop(a, b) {
            var c = a;
            while (c < 20) {
                c += b;
            } // while
            return c;
        } // the_tailrecursive_function_converted_to_a_loop


If a recursion stop condition is not met, a recursion based infinite loop analogue, an infinite recursion, occurs. If recursion occurs not within a single function, but within a set of functions, then the possibility of an infinite recursion, can be difficult for humans to notice, specially if the occurrence of the recursion is not intentional and involves multiple exhaustive components.


        function func_1_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions(a, b) {
            if (20 <= a) { // The recursion stop condition.
                return a;
            } // if
            var c = func_2_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions(a, b);
            return c;
        } // func_1_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions

        function func_2_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions(a, b) {
            var a_new = a + b;
            var c = func_1_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions(a_new, b);
            return c;
        } // func_2_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions


Walking on Trees

If the number of vertices in the tree is not an issue, that is to say, the dataset size is not an issue, then the various simplistic tree-walking algorithms that are presented in various study books, are sufficient. However, there is an analogy with sorting algorithms in the sense that the non-laborous-to-implement bubblesort is fine for smaller datasets, but for real-life data-sets a more complex and more laborous-to-implement algorithm is needed. Just like with sorting algorithms, a general recommendation is to avoid creating a custom implementation, because implementing a proper tree-walker is a laborous effort. An assumption of many tree-walking algorithms is that the tree does not change during the tree-walk and walking takes time regardless of implementation. For file systems that assumption might not hold, specially if multiple operating system processes work on the same folder. A general structure of a primitive tree-walking function might look like this:

        function with_heavy_input_verification_and_comfort_features(various_parameters) {
            // blabla, a lot of code
            function the_actual_recursive_function_that_receives_only_2_vertices(a_vertex,
                                                                                 the_root_vertex_of_the_tree) {
                // The recursion stop condition
                // function can take a look at the sub-vertices of
                // the a_vertex, but that's an implementation detail of
                // the recursion stop condition function.
                if (func_stop_the_recursion_by_condition_1(a_vertex)) {
                    return; // stop the recursion
                } // if
                if (func_stop_the_recursion_by_condition_2(a_vertex)) {
                    return; // stop the recursion
                } // if
                // ...
                // The rest of the code of the recursive function.
            } // the_actual_recursive_function_that_receives_only_2_vertices
            // The various calls to the
            // the_actual_recursive_function_that_receives_only_2_vertices(...)
            // and the implementation of the comfort related features
            return something_that_may_be_different_from_the_recursive_function_output
        } // with_heavy_input_verification_and_comfort_features


A Ruby example of a primitive tree-walking implementation that has been inspired by the book "Head First Design Patterns":

# It allows one to assemble a tree structure and then to iterate
# recursively through it. The iteration can be done by calling
# method "next()" at the root node or by using a "each_node"
# iteration loop at the root node. In terms of design patterns,
# one can see it as a mixture of the "Composite Design Pattern"
# and the "Iterator Design Pattern".
class Kibuvits_iterable_tree_t1_node
   attr_accessor :data_record, :name, :root_node

   # the @next_node is used only in the root node instance
   attr_accessor :parent_node, :next_node, :children

   def initialize
      @root_node=self
      @next_node=self
      @parent_node=self
      @name="nameless"
      @children=Array.new
      @iteration_index=0
   end # initialize

   def add_child(a_child_node)
      a_child_node.parent_node=self
      a_child_node.root_node=@root_node
      @children << a_child_node
   end # add_child

   def each_node(&iteration_loop)
      reset_the_iteration_state
      yield @root_node.next_node
      x=@root_node.next
      while @root_node.next_node!=@root_node do
         yield @root_node.next_node
         x=@root_node.next
      end # loop
   end # each_node()

   # A Java iterator-style next(). If it is called on the root node,
   # it iterates through the entire tree recursively. It returns
   # a node instance.
   def next
      x=@root_node.next_node.next_from_node_instance
      @root_node.next_node=x
      return x
   end # next

   def reset_the_iteration_state
      while @root_node.next_node!=@root_node do
         @root_node.next
      end # loop
   end # reset_the_iteration_state

   protected
   def next_from_node_instance
      answer=""
      if (@children.length-1) < @iteration_index
         @iteration_index=0
         if @root_node==self
            answer=self
         else
            answer=@parent_node.next_from_node_instance
         end # if
      else
         answer=@children[@iteration_index]
         @iteration_index+=1
      end # if
      return answer
   end # next_from_node_instance()

end # class Kibuvits_iterable_tree_t1_node

#=========================================================================
# Sample code:

def create_a_demo_tree
   a=Kibuvits_iterable_tree_t1_node.new
   b=Kibuvits_iterable_tree_t1_node.new
   c=Kibuvits_iterable_tree_t1_node.new
   d=Kibuvits_iterable_tree_t1_node.new
   e=Kibuvits_iterable_tree_t1_node.new
   a.add_child(b)
   a.add_child(d)
   b.add_child(c)
   b.add_child(e)
   a.name="A"
   b.name="B"
   c.name="C"
   d.name="D"
   e.name="E"
   return a
end # create_a_demo_tree

tree=create_a_demo_tree
puts "\n\n--------- Node names by \"each_node\" loop: -----------\n"
tree.each_node {|a_node| print a_node.name}
puts "\n\n--------- Node names by a Java Iterator-like loop: -----------\n"
9.times { x=tree.next; print x.name }
puts "\n\n-- Node names by Java Iterator-like loop after iteration reset: --\n"
tree.reset_the_iteration_state
5.times { x=tree.next; print x.name }
puts "\n\nThe end of story. Thanks for watching. :) \n\n"

#=========================================================================


A real-life tree-walker interface specification example:


INCOMPLETE, POOLELI, lisada siia Kibuvitsa puu-jalutaja liidese spec.


Some Sample code for copy-pasting

<!DOCTYPE HTML>
<html>
<head>
    <title>Recursion Code Examples in JavaScript and HTML5</title>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
    <script type="text/javascript">


        function a_tailrecursive_function(a, b) {
            if (20 <= a) { // Recursion stop condition.
                return a;
            } // if
            var a_new = a + b;
            var c = a_tailrecursive_function(a_new, b);
            return c;
        } // a_tailrecursive_function

        function the_tailrecursive_function_converted_to_a_loop(a, b) {
            var c = a;
            while (c < 20) {
                c += b;
            } // while
            return c;
        } // the_tailrecursive_function_converted_to_a_loop


        function func_1_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions(a, b) {
            if (20 <= a) { // The recursion stop condition.
                return a;
            } // if
            var c = func_2_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions(a, b);
            return c;
        } // func_1_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions

        function func_2_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions(a, b) {
            var a_new = a + b;
            var c = func_1_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions(a_new, b);
            return c;
        } // func_2_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions

        function a_demo_of_a_conditionally_infinite_recursion(a, b) {
            // This is to demonstrate that recursion can be quirky.
            if (20 <= a) {
                return a;
            } // if
            var c = 0;
            if (a <= 15) {
                c = a_demo_of_a_conditionally_infinite_recursion((b + 12), 3);
                // Infinite recursion will not occur, if 4<=b .
            } // if
            var d = a + b + c;
            return d;
        } // a_demo_of_a_conditionally_infinite_recursion


        window.onload = function () {
            var a, b, c = null;
            var s_html = "";
            //--------------------
            s_html = s_html +
            "<br/>a_tailrecursive_function(...) == " +
            a_tailrecursive_function(9, 4); // 9, 13, 17, 21
            //--------------------
            s_html = s_html +
            "<br/>the_tailrecursive_function_converted_to_a_loop(...) == " +
            the_tailrecursive_function_converted_to_a_loop(9, 4);
            //--------------------
            s_html = s_html +
            "<br/>func_1_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions(...) == " +
            func_1_of_a_demo_of_a_recursion_that_occurs_through_multiple_functions(9, 4);
            //--------------------
            b = 4; // 3 will trigger infinite recursion
            s_html = s_html +
            "<br/><br/>a_demo_of_a_conditionally_infinite_recursion(...) == " +
            a_demo_of_a_conditionally_infinite_recursion(9, 4);
            //--------------------
            var ob_p_1 = document.getElementById('id_p_1');
            ob_p_1.innerHTML = s_html;
        } // window.onload

    </script>
</head>
<body>
<p id="id_p_1"></p>
</body>
</html>


Assertions

... have its own chapterr.