Changeset 3791


Ignore:
Timestamp:
Feb 23, 2016 2:05:11 PM (4 years ago)
Author:
bradbell
Message:

merge to branch: trunk
from repository: https://github.com/coin-or/CppAD
start hash code: 1d6dc964379103ffc27725c649e22416e1cd233b
end hash code: b41cff3e1ace54eeb8cc4ed37ed4743594765bad

commit b41cff3e1ace54eeb8cc4ed37ed4743594765bad
Author: Brad Bell <bradbell@…>
Date: Tue Feb 23 11:23:32 2016 -0700

Advance version to cppad-20160223.
whats_new_16.omh: more precise information about speed test results.
main.cpp: increase size of sparse speed tests.

commit 9ca60f31817c4d3a19536534f7e31e1d12f5a0d4
Author: Brad Bell <bradbell@…>
Date: Tue Feb 23 10:31:18 2016 -0700

sparse branch:
Use assignment for union when left or right operand is a subset of the other.

commit 4456948025c577d39f6eadd46ef2d4d7374eff46
Author: Brad Bell <bradbell@…>
Date: Tue Feb 23 08:53:51 2016 -0700

sparse branch:
Test if target for union already has the correct value.

commit f2f000b0ee9c4e1599f231aad3dea1198d28c0fc
Author: Brad Bell <bradbell@…>
Date: Mon Feb 22 16:57:46 2016 -0700

sparse branch:
sparse_list.hpp: remove extra checks used for debugging.

commit 16bc02b6ecc6e2c4fbf3fbb9c779ef0efcb6a16b
Author: Brad Bell <bradbell@…>
Date: Mon Feb 22 10:10:24 2016 -0700

sparse branch:
Add test_more/local for testing features not in user API.
vector_set.cpp: test vector of sets operations.
sparse_list.hpp: user referece counting and list sharing.

Location:
trunk
Files:
2 added
11 edited

Legend:

Unmodified
Added
Removed
  • trunk/AUTHORS

    r3790 r3791  
    22             ===========================================
    33
    4 To date, 2016-02-20, Bradley M. Bell is the sole author of CppAD.
     4To date, 2016-02-23, Bradley M. Bell is the sole author of CppAD.
    55While Bradley M. Bell worked for the University of Washington during
    66the development of CppAD, the following are also true:
  • trunk/CMakeLists.txt

    r3790 r3791  
    1818
    1919# cppad_version is used by set_version.sh to get the version number.
    20 SET(cppad_version      "20160220" )
     20SET(cppad_version      "20160223" )
    2121SET(cppad_url          "http://www.coin-or.org/CppAD" )
    2222SET(cppad_description  "Differentiation of C++ Algorithms" )
  • trunk/configure

    r3790 r3791  
    11#! /bin/sh
    22# Guess values for system-dependent variables and create Makefiles.
    3 # Generated by GNU Autoconf 2.69 for cppad 20160220.
     3# Generated by GNU Autoconf 2.69 for cppad 20160223.
    44#
    55# Report bugs to <cppad@list.coin-or.org>.
     
    581581PACKAGE_NAME='cppad'
    582582PACKAGE_TARNAME='cppad'
    583 PACKAGE_VERSION='20160220'
    584 PACKAGE_STRING='cppad 20160220'
     583PACKAGE_VERSION='20160223'
     584PACKAGE_STRING='cppad 20160223'
    585585PACKAGE_BUGREPORT='cppad@list.coin-or.org'
    586586PACKAGE_URL=''
     
    14081408  # This message is too long to be a string in the A/UX 3.1 sh.
    14091409  cat <<_ACEOF
    1410 \`configure' configures cppad 20160220 to adapt to many kinds of systems.
     1410\`configure' configures cppad 20160223 to adapt to many kinds of systems.
    14111411
    14121412Usage: $0 [OPTION]... [VAR=VALUE]...
     
    14781478if test -n "$ac_init_help"; then
    14791479  case $ac_init_help in
    1480      short | recursive ) echo "Configuration of cppad 20160220:";;
     1480     short | recursive ) echo "Configuration of cppad 20160223:";;
    14811481   esac
    14821482  cat <<\_ACEOF
     
    16121612if $ac_init_version; then
    16131613  cat <<\_ACEOF
    1614 cppad configure 20160220
     1614cppad configure 20160223
    16151615generated by GNU Autoconf 2.69
    16161616
     
    22412241running configure, to aid debugging if configure makes a mistake.
    22422242
    2243 It was created by cppad $as_me 20160220, which was
     2243It was created by cppad $as_me 20160223, which was
    22442244generated by GNU Autoconf 2.69.  Invocation command line was
    22452245
     
    31313131# Define the identity of the package.
    31323132 PACKAGE='cppad'
    3133  VERSION='20160220'
     3133 VERSION='20160223'
    31343134
    31353135
     
    85838583# values after options handling.
    85848584ac_log="
    8585 This file was extended by cppad $as_me 20160220, which was
     8585This file was extended by cppad $as_me 20160223, which was
    85868586generated by GNU Autoconf 2.69.  Invocation command line was
    85878587
     
    86408640ac_cs_config="`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`"
    86418641ac_cs_version="\\
    8642 cppad config.status 20160220
     8642cppad config.status 20160223
    86438643configured by $0, generated by GNU Autoconf 2.69,
    86448644  with options \\"\$ac_cs_config\\"
  • trunk/configure.ac

    r3790 r3791  
    1313dnl Process this file with autoconf to produce a configure script.
    1414dnl   package   version              bug-report
    15 AC_INIT([cppad], [20160220], [cppad@list.coin-or.org])
     15AC_INIT([cppad], [20160223], [cppad@list.coin-or.org])
    1616AM_SILENT_RULES([yes])
    1717
  • trunk/cppad/local/sparse_list.hpp

    r3757 r3791  
    44
    55/* --------------------------------------------------------------------------
    6 CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-15 Bradley M. Bell
     6CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-16 Bradley M. Bell
    77
    88CppAD is distributed under multiple licenses. This distribution is under
     
    1919/*!
    2020\file sparse_list.hpp
    21 Vector of sets of positive integers stored as singly linked lists.
     21Vector of sets of positive integers stored as singly linked lists
     22in with the element values strictly increasing.
    2223*/
    2324
     
    2829class sparse_list {
    2930public:
    30         /// type used for each set in the vector of sets
    31         /// (note that next is index in data_ for next element in this set).
    32         struct pair_size_t { size_t value; size_t next; };
     31        /// type used for each entry in a singly linked list.
     32        struct pair_size_t {
     33                /// For the first entry in each list, this is the reference count.
     34                /// For the other entries in the list this is an element of the set.
     35                size_t value;
     36
     37                /// This is the index in data_ of the next entry in the list.
     38                /// If there are no more entries in the list, this value is zero.
     39                /// (The first entry in data_ is not used.)
     40                size_t next;
     41        };
    3342private:
    3443        // -----------------------------------------------------------------
    35         /// Number of sets that we are representing
    36         /// (set by constructor and resize).
    37         size_t n_set_;
    38 
    3944        /// Possible elements in each set are 0, 1, ..., end_ - 1;
    4045        size_t end_;
    4146
    42         /// The data for all the elements in all the sets
     47        /// This index is used as an iterator for one list and points to the
     48        /// next pair for the list.
     49        pair_size_t next_pair_;
     50
     51        /// number of elements in data_ that have been allocated
     52        /// and are no longer being used.
     53        size_t data_not_used_;
     54
     55        /*!
     56        The number of elements in this vector is the number of sets,
     57        which is also the number of singly linked lists.
     58
     59        \li
     60        If the i-th set has no elements, start_[i] is zero.
     61
     62        \li
     63        If the i-th set is non-empty, start_[i] is the index in data_
     64        for the first entry in the i-th singly linked list for this set.
     65        In this case and data_[ start_[i] ].value is the reference count
     66        for this list and data_[ start_[i] ].next is not zero becasue there
     67        is at least one entry in this list.
     68        */
     69        CppAD::pod_vector<size_t> start_;
     70
     71        /// The data for all the singly linked lists.
    4372        CppAD::pod_vector<pair_size_t> data_;
    4473
    45         /// next element
    46         pair_size_t next_pair_;
    47 
    48         /// number of elements in data_ that are no longer being used.
    49         size_t data_not_used_;
    50 
    51         /// temporary data vector used for garbage collection
    52         CppAD::pod_vector<pair_size_t> data_tmp_;
    53         // -----------------------------------------------------------------
    54         /*! Private member function that counts number of elements in a set.
     74        // -----------------------------------------------------------------
     75        /*!
     76        Private member functiont that counts references to sets.
    5577
    5678        \param index
    57         is the index of the set we are counting.
    58 
    59         \par Checked Assertions
    60         \li index < n_set_
     79        is the index of the set that we are counting the references to.
     80
     81        \return
     82        if the set is empty, the return value is empty.
     83        Otherwise it is the number of sets that share the same linked list
     84        */
     85        size_t reference_count(size_t index) const
     86        {       size_t ret = start_[index];
     87                if( ret != 0 )
     88                {       CPPAD_ASSERT_UNKNOWN( data_[ret].value != 0 );
     89                        CPPAD_ASSERT_UNKNOWN( data_[ret].next != 0 );
     90                        ret = data_[ret].value;
     91                }
     92                return ret;
     93        }
     94        // -----------------------------------------------------------------
     95        /*!
     96        Private member function that counts number of elements in a set.
     97
     98        \param index
     99        is the index in start_ of the set we are counting the elements of.
    61100        */
    62101        size_t number_elements(size_t index) const
    63         {       CPPAD_ASSERT_UNKNOWN(index < n_set_ );
     102        {       CPPAD_ASSERT_UNKNOWN(index < start_.size() );
    64103
    65104                size_t count   = 0;
    66                 size_t i       = index;
    67                 size_t value = data_[i].value;
     105                size_t start   = start_[index];
     106
     107                // check if the set is empty
     108                if( start == 0 )
     109                        return count;
     110                CPPAD_ASSERT_UNKNOWN( reference_count(index) > 0 );
     111
     112                // advance to the first element in the set
     113                size_t next    = data_[start].next;
     114                while( next != 0 )
     115                {       CPPAD_ASSERT_UNKNOWN( data_[next].value < end_ );
     116                        count++;
     117                        next  = data_[next].next;
     118                }
     119                CPPAD_ASSERT_UNKNOWN( count > 0 );
     120                return count;
     121        }
     122        // -----------------------------------------------------------------
     123        /*!
     124        Member function that checks the number of data elements not used
     125        (effectively const, but modifies and restores values)
     126        */
     127        void check_data_not_used(void)
     128        {       // number of sets
     129                size_t n_set = start_.size();
     130                //
     131                // save the reference counters
     132                pod_vector<size_t> ref_count;
     133                ref_count.extend(n_set);
     134                for(size_t i = 0; i < n_set; i++)
     135                        ref_count[i] = reference_count(i);
     136
     137                // count the number of entries in the singly linked lists
     138                size_t number_list_entries = 0;
     139                for(size_t i = 0; i < start_.size(); i++)
     140                {       size_t start = start_[i];
     141                        if( start != 0 )
     142                        {       CPPAD_ASSERT_UNKNOWN( data_[start].value > 0 );
     143                                // decrement the reference counter
     144                                data_[start].value--;
     145                                // copy the list when we hit zero
     146                                if( data_[start].value == 0 )
     147                                {       // This should be the last reference to this linked list.
     148                                        // Restore reference count
     149                                        data_[start].value = ref_count[i];
     150                                        // count number of entries in this list
     151                                        // (is one more than number in set)
     152                                        number_list_entries += number_elements(i) + 1;
     153                                }
     154                        }
     155                }
     156                CPPAD_ASSERT_UNKNOWN(
     157                        number_list_entries + data_not_used_ == data_.size()
     158                );
     159                return;
     160        }
     161        // -----------------------------------------------------------------
     162        /*!
     163        Check if one of two sets is a subset of the other set
     164
     165        \param one_this
     166        is the index in this sparse_list object of the first set.
     167
     168        \param two_other
     169        is the index in other sparse_list object of the second set.
     170
     171        \param other
     172        is the other sparse_list object (which may be the same as this
     173        sparse_list object).
     174
     175        \return
     176        If zero, niether set is a subset of the other.
     177        If one, then set one is a subset of set two.
     178        If two, then set two is a subset of set one.
     179        If the two sets are equal, the value two is returned; i.e., the set
     180        in the other object is identified as a subset of the set in this object.
     181        */
     182        size_t is_subset(
     183                size_t                  one_this    ,
     184                size_t                  two_other   ,
     185                const sparse_list&      other       ) const
     186        {
     187                CPPAD_ASSERT_UNKNOWN( one_this  < start_.size()         );
     188                CPPAD_ASSERT_UNKNOWN( two_other < other.start_.size()   );
     189                CPPAD_ASSERT_UNKNOWN( end_  == other.end_               );
     190                //
     191                // start
     192                size_t start_one    = start_[one_this];
     193                size_t start_two    = other.start_[two_other];
     194                if( start_two == 0 )
     195                        return 2;
     196                if( start_one == 0 )
     197                        return 1;
     198                //
     199                // next
     200                size_t next_one     = data_[start_one].next;
     201                size_t next_two     = other.data_[start_two].next;
     202                //
     203                // value
     204                size_t value_one    = data_[next_one].value;
     205                size_t value_two    = other.data_[next_two].value;
     206                //
     207                bool one_subset     = true;
     208                bool two_subset     = true;
     209
     210                size_t value_union = std::min(value_one, value_two);
     211                while( (one_subset | two_subset) & (value_union < end_) )
     212                {       if( value_one > value_union )
     213                                two_subset = false;
     214                        else
     215                        {       next_one = data_[next_one].next;
     216                                if( next_one == 0 )
     217                                        value_one = end_;
     218                                else
     219                                        value_one = data_[next_one].value;
     220                        }
     221                        if( value_two > value_union )
     222                                one_subset = false;
     223                        else
     224                        {       next_two = other.data_[next_two].next;
     225                                if( next_two == 0 )
     226                                        value_two = end_;
     227                                else
     228                                        value_two = other.data_[next_two].value;
     229                        }
     230                        value_union = std::min(value_one, value_two);
     231                }
     232                if( two_subset )
     233                        return 2;
     234                if( one_subset )
     235                        return 1;
     236                return 0;
     237        }
     238        // -----------------------------------------------------------------
     239        /*!
     240        Private member functions that does garbage collection.
     241
     242        This routine should be called when the number entries in data_
     243        that are not being used is greater that data_.size() / 2.
     244
     245        Note that the size of data_ should equal the number of entries
     246        in the singly linked lists plust the number of entries in data_
     247        that are not being used. (Note that data_[0] never gets used.)
     248        */
     249        void collect_garbage(void)
     250        {       CPPAD_ASSERT_UNKNOWN( data_not_used_ > data_.size() / 2 );
     251# ifndef NDEBUG
     252                check_data_not_used();
     253# endif
     254                //
     255                // number of sets including empty ones
     256                size_t n_set  = start_.size();
     257                //
     258                // copy the sets to a temporary data vector
     259                pod_vector<pair_size_t> data_tmp;
     260                data_tmp.extend(1); // data_tmp[0] will not be used
     261                //
     262                pod_vector<size_t> start_tmp;
     263                start_tmp.extend(n_set);
     264                for(size_t i = 0; i < n_set; i++)
     265                {       size_t start    = start_[i];
     266                        if( start == 0 )
     267                                start_tmp[i] = 0;
     268                        else
     269                        {       // check if this linked list has already been copied
     270                                if( data_[start].next == 0 )
     271                                {       // starting address in data_tmp has been stored here
     272                                        start_tmp[i] = data_[start].value;
     273                                }
     274                                else
     275                                {       size_t count              = data_[start].value;
     276                                        size_t next               = data_[start].next;
     277                                        //
     278                                        size_t tmp_start          = data_tmp.extend(2);
     279                                        size_t next_tmp           = tmp_start + 1;
     280                                        start_tmp[i]              = tmp_start;
     281                                        data_tmp[tmp_start].value = count;
     282                                        data_tmp[tmp_start].next  = next_tmp;
     283                                        //
     284                                        CPPAD_ASSERT_UNKNOWN( next != 0 );
     285                                        while( next != 0 )
     286                                        {       CPPAD_ASSERT_UNKNOWN( data_[next].value < end_ );
     287                                                data_tmp[next_tmp].value = data_[next].value;
     288                                                //
     289                                                next                      = data_[next].next;
     290                                                if( next == 0 )
     291                                                        data_tmp[next_tmp].next = 0;
     292                                                else
     293                                                {       // data_tmp[next_tmp].next  = data_tmp.extend(1);
     294                                                        // does not seem to work ?
     295                                                        size_t tmp               = data_tmp.extend(1);
     296                                                        data_tmp[next_tmp].next  = tmp;
     297                                                        next_tmp                 = tmp;
     298                                                }
     299                                        }
     300                                        // store the starting address here
     301                                        data_[start].value = tmp_start;
     302                                        // flag that indicates this link list already copied
     303                                        data_[start].next = 0;
     304                                }
     305                        }
     306                }
     307
     308                // swap the tmp and old data vectors
     309                start_.swap(start_tmp);
     310                data_.swap(data_tmp);
     311
     312                // all of the elements, except the first, are used
     313                data_not_used_ = 1;
     314        }
     315        // -----------------------------------------------------------------
     316        /*!
     317        Make a separate copy of the shared list
     318
     319        \param index
     320        is the index, in the vector of sets, for this list.
     321        */
     322        void separate_copy(size_t index)
     323        {       size_t ref_count = reference_count(index);
     324                if( ref_count <= 1 )
     325                        return;
     326                //
     327                size_t start = start_[index];
     328                size_t next  = data_[start].next;
     329                size_t value = data_[next].value;
     330                //
     331                size_t copy_cur       = data_.extend(2);
     332                size_t copy_next      = copy_cur + 1;
     333                start_[index]         = copy_cur;
     334                data_[copy_cur].value = 1;
     335                data_[copy_cur].next  = copy_next;
     336                copy_cur              = copy_next;
     337                //
     338                CPPAD_ASSERT_UNKNOWN( value < end_ );
    68339                while( value < end_ )
    69                 {       count++;
    70                         i     = data_[i].next;
    71                         value = data_[i].value;
    72                 }
    73                 return count;
    74         }
    75         // -----------------------------------------------------------------
    76         /// Private member functions that does garbage collection.
    77         void collect_garbage(void)
    78         {       CPPAD_ASSERT_UNKNOWN( 2 * data_not_used_ > data_.size() );
    79                 //
    80                 CPPAD_ASSERT_UNKNOWN(
    81                         number_elements() + n_set_ + data_not_used_ == data_.size()
    82                 );
    83 
    84                 // copy the sets to a temporary data vector
    85                 data_tmp_.erase();
    86                 data_tmp_.extend(n_set_);
    87                 for(size_t i = 0; i < n_set_; i++)
    88                 {       size_t next     = i;
    89                         size_t next_tmp = i;
     340                {       data_[copy_cur].value   = value;
    90341                        //
    91                         size_t value    = data_[next].value;
    92                         while( value < end_ )
    93                         {       data_tmp_[next_tmp].value = value;
    94                                 // data_tmp_[next_tmp].next  = data_tmp_.extend(1);
    95                                 // does not seem to work ?
    96                                 size_t index_tmp         = data_tmp_.extend(1);
    97                                 data_tmp_[next_tmp].next = index_tmp;
    98                                 //
    99                                 next                     = data_[next].next;
    100                                 next_tmp                 = data_tmp_[next_tmp].next;
    101                                 //
    102                                 value                    = data_[next].value;
    103                         }
    104                         data_tmp_[next_tmp].value = end_;
    105                 }
    106                 CPPAD_ASSERT_UNKNOWN(
    107                         data_tmp_.size() + data_not_used_ == data_.size()
    108                 );
    109 
    110                 // swap the tmp and old data vectors
    111                 data_.swap(data_tmp_);
    112 
    113                 // all of the elements are used in this new version of data_
    114                 data_not_used_ = 0;
     342                        next       = data_[next].next;
     343                        if( next == 0 )
     344                        {       value = end_;
     345                                data_[copy_cur].next = 0;
     346                        }
     347                        else
     348                        {       value  = data_[next].value;
     349                                data_[copy_cur].next = data_.extend(1);
     350                        }
     351                }
     352                CPPAD_ASSERT_UNKNOWN( next == 0 );
     353                //
     354                // decrement reference count
     355                CPPAD_ASSERT_UNKNOWN( data_[start].value == ref_count );
     356                data_[start].value--;
     357                //
     358        }
     359        // -----------------------------------------------------------------
     360        /*! Using copy constructor is a programing (not user) error
     361
     362        \param v
     363        vector of sets that we are attempting to make a copy of.
     364        */
     365        sparse_list(const sparse_list& v)
     366        {       // Error: Probably a sparse_list argument has been passed by value
     367                CPPAD_ASSERT_UNKNOWN(false);
    115368        }
    116369public:
     
    119372        */
    120373        sparse_list(void) :
    121         n_set_(0)                 ,
    122374        end_(0)                   ,
    123375        data_not_used_(0)
    124         {       next_pair_.value = end_; }
    125         // -----------------------------------------------------------------
    126         /*! Using copy constructor is a programing (not user) error
    127 
    128         \param v
    129         vector that we are attempting to make a copy of.
    130         */
    131         sparse_list(const sparse_list& v)
    132         {       // Error:
    133                 // Probably a sparse_list argument has been passed by value
    134                 CPPAD_ASSERT_UNKNOWN(false);
    135         }
    136         // -----------------------------------------------------------------
    137         /*! Destructor
    138         */
     376        {       next_pair_.next = 0; }
     377        // -----------------------------------------------------------------
     378        /// Destructor
    139379        ~sparse_list(void)
    140380        { }
    141381        // -----------------------------------------------------------------
    142         /*! Change number of sets, end marker, and initialize all sets as empty
    143 
    144         If \c n_set_in is zero, any memory currently allocated for this object
    145         is freed. Otherwise, new memory may be allocated for the sets (if needed).
     382        /*!
     383        Start a new vector of sets.
    146384
    147385        \param n_set_in
    148386        is the number of sets in this vector of sets.
     387        \li
     388        If n_set_in is zero, any memory currently allocated for this object
     389        is freed. Otherwise, new memory may be allocated for the sets (if needed).
     390        \li
     391        If n_set_in is non-zero, a vector of n_set_in is created and all
     392        the sets are initilaized as empty.
    149393
    150394        \param end_in
     
    152396        */
    153397        void resize(size_t n_set_in, size_t end_in)
    154         {       n_set_                 = n_set_in;
     398        {       if( n_set_in == 0 )
     399                {       // restore object to start after constructor
     400                        // (no memory allocated for this object)
     401                        data_.free();
     402                        start_.free();
     403                        data_not_used_  = 0;
     404                        end_            = 0;
     405                        //
     406                        next_pair_.next = 0;
     407                        return;
     408                }
    155409                end_                   = end_in;
    156                 next_pair_.value       = end_in;
    157                 data_not_used_         = 0;
    158                 if( n_set_in == 0 )
    159                 {       // free all memory connected with this object
    160                         data_.free();
    161                         return;
    162                 }
    163                 // now start a new vector with empty sets
     410                next_pair_.next        = 0;
     411                //
     412                start_.erase();
     413                start_.extend(n_set_in);
     414                for(size_t i = 0; i < n_set_in; i++)
     415                        start_[i] = 0;
     416                //
    164417                data_.erase();
    165                 data_.extend(n_set_);
    166                 for(size_t i = 0; i < n_set_; i++)
    167                         data_[i].value = end_;
    168         }
    169         // -----------------------------------------------------------------
    170         /*! Add one element to a set.
     418                data_.extend(1); // first element is not used
     419                data_not_used_  = 1;
     420        }
     421        // -----------------------------------------------------------------
     422        /*!
     423        check an element is in a set.
    171424
    172425        \param index
     
    174427
    175428        \param element
    176         is the element we are adding to the set.
    177 
    178         \par Checked Assertions
    179         \li index    < n_set_
    180         \li element  < end_
    181         */
    182         void add_element(size_t index, size_t element)
    183         {       CPPAD_ASSERT_UNKNOWN( index   < n_set_ );
     429        is the element we are checking to see if it is in the set.
     430        */
     431        bool is_element(size_t index, size_t element) const
     432        {       CPPAD_ASSERT_UNKNOWN( index   < start_.size() );
    184433                CPPAD_ASSERT_UNKNOWN( element < end_ );
    185 
    186                 size_t value = data_[index].value;
    187 
    188                 // case of inserting at beginning
    189                 if( element < value )
    190                 {       size_t insert       = data_.extend(1);
    191                         data_[insert]       = data_[index];
    192                         data_[index].value  = element;
    193                         data_[index].next   = insert;
    194                         return;
    195                 }
    196 
    197                 // search list for place to insert
    198                 size_t  previous = index;
    199                 size_t  current  = data_[previous].next;
    200                 value            = data_[current].value;
     434                //
     435                size_t start = start_[index];
     436                if( start == 0 )
     437                        return false;
     438                //
     439                CPPAD_ASSERT_UNKNOWN( data_[start].value > 0 );
     440                CPPAD_ASSERT_UNKNOWN( data_[start].next > 0 );
     441                //
     442                size_t next  = data_[start].next;
     443                size_t value = data_[next].value;
    201444                while( value < element )
    202                 {       previous = current;
    203                         current = data_[previous].next;
    204                         value   = data_[current].value;
    205                 }
    206                 if( element != value )
    207                 {       CPPAD_ASSERT_UNKNOWN( element < value );
    208                         size_t insert         = data_.extend(1);
    209                         //
    210                         data_[insert].next    = data_[previous].next;
    211                         data_[previous].next  = insert;
    212                         data_[insert].value   = element;
    213                 }
    214         }
    215         // -----------------------------------------------------------------
    216         /*! Is an element in a set.
     445                {       next  = data_[next].next;
     446                        if( next == 0 )
     447                                value = end_;
     448                        else
     449                                value = data_[next].value;
     450                }
     451                return element == value;
     452        }
     453        // -----------------------------------------------------------------
     454        /*!
     455        Add one element to a set.
    217456
    218457        \param index
     
    220459
    221460        \param element
    222         is the element we are checking to see if it is in set.
    223 
    224         \par Checked Assertions
    225         \li index    < n_set_
    226         \li element  < end_
    227         */
    228         bool is_element(size_t index, size_t element)
    229         {       CPPAD_ASSERT_UNKNOWN( index   < n_set_ );
     461        is the element we are adding to the set.
     462        */
     463        void add_element(size_t index, size_t element)
     464        {       CPPAD_ASSERT_UNKNOWN( index   < start_.size() );
    230465                CPPAD_ASSERT_UNKNOWN( element < end_ );
    231466
    232                 size_t i     = index;
    233                 size_t value = data_[i].value;
     467                // check if element is already in the set
     468                if( is_element(index, element) )
     469                        return;
     470
     471                // check for case where starting set is empty
     472                size_t start = start_[index];
     473                if( start == 0 )
     474                {       start         = data_.extend(2);
     475                        start_[index] = start;
     476                        size_t next   = start + 1;
     477                        data_[start].value = 1; // reference count
     478                        data_[start].next  = next;
     479                        data_[next].value  = element;
     480                        data_[next].next   = 0;
     481                        return;
     482                }
     483                // make sure that we have a separate copy of this set
     484                separate_copy(index);
     485                //
     486                CPPAD_ASSERT_UNKNOWN( reference_count(index) == 1 );
     487                size_t previous = start_[index];
     488                size_t next     = data_[start].next;
     489                size_t value    = data_[next].value;
     490                CPPAD_ASSERT_UNKNOWN( value < end_ );
    234491                while( value < element )
    235                 {       i     = data_[i].next;
    236                         value = data_[i].value;
    237                 }
    238 
    239                 return element == value;
     492                {       previous = next;
     493                        next     = data_[next].next;
     494                        if( next == 0 )
     495                                value = end_;
     496                        else
     497                                value = data_[next].value;
     498                }
     499                CPPAD_ASSERT_UNKNOWN( element < value )
     500                //
     501                size_t insert         = data_.extend(1);
     502                data_[insert].next    = next;
     503                data_[previous].next  = insert;
     504                data_[insert].value   = element;
     505                //
    240506        }
    241507        // -----------------------------------------------------------------
     
    245511        is the index for the set that is going to be retrieved.
    246512        The elements of the set are retrieved in increasing order.
    247 
    248         \par Checked Assertions
    249         \li index  < n_set_
    250 
    251513        */
    252514        void begin(size_t index)
    253515        {       // initialize element to search for in this set
    254                 CPPAD_ASSERT_UNKNOWN( index < n_set_ );
    255                 next_pair_  = data_[index];
    256 
     516                CPPAD_ASSERT_UNKNOWN( index < start_.size() );
     517                size_t start = start_[index];
     518                if( start == 0 )
     519                        next_pair_.next = 0;
     520                else
     521                {       CPPAD_ASSERT_UNKNOWN( reference_count(index) > 0 );
     522                        next_pair_.next  = data_[start].next;
     523                }
    257524                return;
    258525        }
    259526        // -----------------------------------------------------------------
    260         /*! Get the next element from the current retrieval set.
     527        /*!
     528        Get the next element from the current retrieval set.
    261529
    262530        \return
    263531        is the next element in the set with index
    264         specified by the previous call to \c begin.
    265         If no such element exists, \c this->end() is returned.
     532        specified by the previous call to begin.
     533        If no such element exists, this->end() is returned.
    266534
    267535        \par Assumption
    268         There is no call to \c add_element or \c binary_union
    269         since the previvious \c begin
     536        There is no call to add_element or binary_union
     537        since the previvious begin
    270538        */
    271539        size_t next_element(void)
    272         {       size_t element = next_pair_.value;
    273                 if( element != end_ )
    274                         next_pair_ = data_[next_pair_.next];
     540        {       if( next_pair_.next == 0 )
     541                        return end_;
     542
     543                next_pair_     = data_[next_pair_.next];
     544                size_t element = next_pair_.value;
    275545
    276546                return element;
     
    283553
    284554        \par data_not_used_
    285         increments this value by number of elements lost.
    286 
    287         \par Checked Assertions
    288         \li target < n_set_
     555        increments this value by number of data_ elements that are lost
     556        (unlinked) by this operation.
    289557        */
    290558        void clear(size_t target)
    291         {       CPPAD_ASSERT_UNKNOWN( target < n_set_ );
    292 
    293                 // number of elements that will be deleted by this operation
    294                 size_t number_delete = number_elements(target);
    295 
    296                 // delete the elements from the set
    297                 data_[target].value = end_;
    298 
    299                 // adjust data_not_used_
    300                 data_not_used_ += number_delete;
    301 
    302                 if( 2 * data_not_used_ > data_.size() )
    303                         collect_garbage();
     559        {       CPPAD_ASSERT_UNKNOWN( target < start_.size() );
     560
     561                // number of references to this set
     562                size_t ref_count = reference_count(target);
     563
     564                // case by reference count
     565                if( ref_count > 1  )
     566                {       // just remove this reference
     567                        size_t start   = start_[target];
     568                        start_[target] = 0;
     569                        CPPAD_ASSERT_UNKNOWN( data_[start].value == ref_count );
     570                        data_[start].value--;
     571                }
     572                else if( ref_count == 1 )
     573                {
     574                        // number of data_ elements that will be lost by this operation
     575                        size_t number_delete = number_elements(target) + 1;
     576
     577                        // delete the elements from the set
     578                        start_[target] = 0;
     579
     580                        // adjust data_not_used_
     581                        data_not_used_ += number_delete;
     582
     583                        if( data_not_used_ > data_.size() / 2 )
     584                                collect_garbage();
     585                }
     586                //
    304587        }
    305588        // -----------------------------------------------------------------
     
    307590
    308591        \param this_target
    309         is the index (in this \c sparse_list object) of the set being assinged.
     592        is the index in this sparse_list object of the set being assinged.
    310593
    311594        \param other_source
    312         is the index (in the other \c sparse_list object) of the
    313         that we are using as the value to assign to the target set.
     595        is the index in the other \c sparse_list object of the
     596        set that we are using as the value to assign to the target set.
    314597
    315598        \param other
    316         is the other \c sparse_list object (which may be the same as this
    317         \c sparse_list object).
     599        is the other sparse_list object (which may be the same as this
     600        sparse_list object). This must have the same value for end_.
    318601
    319602        \par data_not_used_
    320603        increments this value by number of elements lost.
    321 
    322         \par Checked Assertions
    323         \li this_target  < n_set_
    324         \li other_index  < other.n_set_
    325604        */
    326605        void assignment(
     
    328607                size_t               other_source ,
    329608                const sparse_list&   other        )
    330         {       CPPAD_ASSERT_UNKNOWN( this_target  <   n_set_        );
    331                 CPPAD_ASSERT_UNKNOWN( other_source <   other.n_set_  );
    332                 CPPAD_ASSERT_UNKNOWN( end_        == other.end()   );
     609        {       CPPAD_ASSERT_UNKNOWN( this_target  <   start_.size()        );
     610                CPPAD_ASSERT_UNKNOWN( other_source <   other.start_.size()  );
     611                CPPAD_ASSERT_UNKNOWN( end_        == other.end_   );
    333612
    334613                // check if we are assigning a set to itself
     
    336615                        return;
    337616
    338                 // number of elements that will be deleted by this operation
    339                 size_t number_delete = number_elements(this_target);
    340 
    341                 size_t this_index        = this_target;
    342                 size_t other_index       = other_source;
    343                 size_t value             = other.data_[other_index].value;
    344                 while( value != end_ )
    345                 {       size_t next             = data_.extend(1);
    346                         data_[this_index].value = value;
    347                         data_[this_index].next  = next;
    348                         this_index              = next;
    349                         other_index             = other.data_[other_index].next;
    350                         value                   = other.data_[other_index].value;
    351                 }
    352                 data_[this_index].value = end_;
     617                // number of list elements that will be deleted by this operation
     618                size_t number_delete = 0;
     619                size_t ref_count     = reference_count(this_target);
     620                size_t start         = start_[this_target];
     621                if( ref_count == 1 )
     622                        number_delete = number_elements(this_target) + 1;
     623                else if (ref_count > 1 )
     624                {       // decrement reference counter
     625                        CPPAD_ASSERT_UNKNOWN( data_[start].value > 1 )
     626                        data_[start].value--;
     627                }
     628
     629                // If this and other are the same, use another reference to same list
     630                size_t other_start = other.start_[other_source];
     631                if( this == &other )
     632                {       start_[this_target] = other_start;
     633                        if( other_start != 0 )
     634                        {       data_[other_start].value++; // increment reference count
     635                                CPPAD_ASSERT_UNKNOWN( data_[other_start].value > 1 );
     636                        }
     637                }
     638                else if( other_start  == 0 )
     639                {       // the target list is empty
     640                        start_[this_target] = 0;
     641                }
     642                else
     643                {       // make a copy of the other list in this sparse_list
     644                        size_t this_start = data_.extend(2);
     645                        size_t this_next  = this_start + 1;
     646                        start_[this_target]     = this_start;
     647                        data_[this_start].value = 1; // reference count
     648                        data_[this_start].next  = this_next;
     649                        //
     650                        size_t next  = other.data_[other_start].next;
     651                        CPPAD_ASSERT_UNKNOWN( next != 0 );
     652                        while( next != 0 )
     653                        {       data_[this_next].value = other.data_[next].value;
     654                                next                   = other.data_[next].next;
     655                                if( next == 0 )
     656                                        data_[this_next].next = 0;
     657                                else
     658                                {       size_t tmp = data_.extend(1);
     659                                        data_[this_next].next = tmp;
     660                                        this_next             = tmp;
     661                                }
     662                        }
     663                }
    353664
    354665                // adjust data_not_used_
    355666                data_not_used_ += number_delete;
    356667
    357                 if( 2 * data_not_used_ > data_.size() )
     668                // check if time for garbage collection
     669                if( data_not_used_ > data_.size() / 2 )
    358670                        collect_garbage();
     671                //
    359672        }
    360673        // -----------------------------------------------------------------
     
    362675
    363676        \param this_target
    364         is the index (in this \c sparse_list object) of the set being assinged.
     677        is the index in this sparse_list object of the set being assinged.
    365678
    366679        \param this_left
    367         is the index (in this \c sparse_list object) of the
     680        is the index in this sparse_list object of the
    368681        left operand for the union operation.
    369         It is OK for \a this_target and \a this_left to be the same value.
     682        It is OK for this_target and this_left to be the same value.
    370683
    371684        \param other_right
    372         is the index (in the other \c sparse_list object) of the
     685        is the index in the other sparse_list object of the
    373686        right operand for the union operation.
    374         It is OK for \a this_target and \a other_right to be the same value.
     687        It is OK for this_target and other_right to be the same value.
    375688
    376689        \param other
    377         is the other \c sparse_list object (which may be the same as this
    378         \c sparse_list object).
    379 
    380         \par Checked Assertions
    381         \li this_target <  n_set_
    382         \li this_left   <  n_set_
    383         \li other_right <  other.n_set_
     690        is the other sparse_list object (which may be the same as this
     691        sparse_list object).
    384692        */
    385693        void binary_union(
     
    389697                const sparse_list&      other        )
    390698        {
    391                 CPPAD_ASSERT_UNKNOWN( this_target < n_set_         );
    392                 CPPAD_ASSERT_UNKNOWN( this_left   < n_set_         );
    393                 CPPAD_ASSERT_UNKNOWN( other_right < other.n_set_   );
    394                 CPPAD_ASSERT_UNKNOWN( end_        == other.end()   );
    395 
    396                 // determine if we will delete the original version of the target
     699                CPPAD_ASSERT_UNKNOWN( this_target < start_.size()         );
     700                CPPAD_ASSERT_UNKNOWN( this_left   < start_.size()         );
     701                CPPAD_ASSERT_UNKNOWN( other_right < other.start_.size()   );
     702                CPPAD_ASSERT_UNKNOWN( end_        == other.end_           );
     703
     704                // check if one of the two operands is a subset of the the other
     705                size_t subset = is_subset(this_left, other_right, other);
     706
     707                // case where right is a subset of left or right and left are equal
     708                if( subset == 2 )
     709                {       assignment(this_target, this_left, *this);
     710                        return;
     711                }
     712                // case where the left is a subset of right and they are not equal
     713                if( subset == 1 )
     714                {       assignment(this_target, other_right, other);
     715                        return;
     716                }
     717                // if niether case holds, then both left and right are non-empty
     718                CPPAD_ASSERT_UNKNOWN( reference_count(this_left) > 0 );
     719                CPPAD_ASSERT_UNKNOWN( other.reference_count(other_right) > 0 );
     720
     721                // must get all the start indices before modify start_this
     722                // (incase start_this is the same as start_left or start_right)
     723                size_t start_target  = start_[this_target];
     724                size_t start_left    = start_[this_left];
     725                size_t start_right   = other.start_[other_right];
     726
     727
     728                // number of list elements that will be deleted by this operation
    397729                size_t number_delete = 0;
    398                 bool delete_target = this_target == this_left;
    399                 delete_target     |= (this == &other) & (this_target == other_right);
    400                 if( delete_target )
    401                 {       // number of elements that will be deleted by this operation
    402                         number_delete = number_elements(this_target);
    403                 }
    404 
    405                 // value and next for left and right sets
    406                 size_t left_value  = data_[this_left].value;
    407                 size_t left_next   = data_[this_left].next;
    408                 size_t right_value = other.data_[other_right].value;
    409                 size_t right_next  = other.data_[other_right].next;
    410 
    411                 // merge left and right sets to form new target set
    412                 size_t current       = this_target;
    413                 while( (left_value < end_) | (right_value < end_) )
    414                 {       if( left_value == right_value )
    415                         {       right_value = other.data_[right_next].value;
    416                                 right_next  = other.data_[right_next].next;
    417                         }
    418                         size_t next         = data_.extend(1);
    419                         data_[current].next = next;
    420                         if( left_value < right_value )
    421                         {       data_[current].value = left_value;
    422                                 left_value           = data_[left_next].value;
    423                                 left_next            = data_[left_next].next;
     730                size_t ref_count     = reference_count(this_target);
     731                if( ref_count == 1 )
     732                        number_delete = number_elements(this_target) + 1;
     733                else if (ref_count > 1 )
     734                {       // decrement reference counter
     735                        CPPAD_ASSERT_UNKNOWN( data_[start_target].value > 1 )
     736                        data_[start_target].value--;
     737                }
     738
     739                // start the new list
     740                size_t start        = data_.extend(1);
     741                size_t next         = start;
     742                start_[this_target] = start;
     743                data_[start].value  = 1; // reference count
     744
     745                // next for left and right lists
     746                size_t next_left   = data_[start_left].next;
     747                size_t next_right  = other.data_[start_right].next;
     748
     749                // value for left and right sets
     750                size_t value_left  = data_[next_left].value;
     751                size_t value_right = other.data_[next_right].value;
     752
     753                CPPAD_ASSERT_UNKNOWN( value_left < end_ && value_right < end_ );
     754                while( (value_left < end_) | (value_right < end_) )
     755                {       if( value_left == value_right )
     756                        {       // advance right so left and right are no longer equal
     757                                next_right  = other.data_[next_right].next;
     758                                if( next_right == 0 )
     759                                        value_right = end_;
     760                                else
     761                                        value_right = other.data_[next_right].value;
     762                        }
     763                        if( value_left < value_right )
     764                        {       size_t tmp        = data_.extend(1);
     765                                data_[next].next  = tmp;
     766                                next              = tmp;
     767                                data_[next].value = value_left;
     768                                // advance left to its next element
     769                                next_left  = data_[next_left].next;
     770                                if( next_left == 0 )
     771                                        value_left       = end_;
     772                                else
     773                                        value_left = data_[next_left].value;
    424774                        }
    425775                        else
    426                         {       data_[current].value = right_value;
    427                                 right_value = other.data_[right_next].value;
    428                                 right_next  = other.data_[right_next].next;
    429                         }
    430                         current = next;
    431                 }
    432                 data_[current].value = end_;
     776                        {       CPPAD_ASSERT_UNKNOWN( value_right < value_left )
     777                                size_t tmp        = data_.extend(1);
     778                                data_[next].next  = tmp;
     779                                next              = tmp;
     780                                data_[next].value = value_right;
     781                                // advance right to its next element
     782                                next_right  = other.data_[next_right].next;
     783                                if( next_right == 0 )
     784                                        value_right = end_;
     785                                else
     786                                        value_right = other.data_[next_right].value;
     787                        }
     788                }
     789                data_[next].next = 0;
    433790
    434791                // adjust data_not_used_
    435792                data_not_used_ += number_delete;
    436793
    437                 if( 2 * data_not_used_ > data_.size() )
     794                if( data_not_used_ > data_.size() / 2 )
    438795                        collect_garbage();
    439         }
     796                //
     797        }
     798        // -----------------------------------------------------------------
     799        /*! Fetch n_set for vector of sets object.
     800
     801        \return
     802        Number of from sets for this vector of sets object
     803        */
     804        size_t n_set(void) const
     805        {       return start_.size(); }
     806        // -----------------------------------------------------------------
     807        /*! Fetch end for this vector of sets object.
     808
     809        \return
     810        is the maximum element value plus one (the minimum element value is 0).
     811        */
     812        size_t end(void) const
     813        {       return end_; }
    440814        // -----------------------------------------------------------------
    441815        /*! Sum over all sets of the number of elements
     
    447821        {       size_t i, count;
    448822                count = 0;
    449                 for(i = 0; i < n_set_; i++)
     823                for(i = 0; i < start_.size(); i++)
    450824                        count += number_elements(i);
    451825                return count;
    452826        }
    453         // -----------------------------------------------------------------
    454         /*! Fetch n_set for vector of sets object.
    455 
    456         \return
    457         Number of from sets for this vector of sets object
    458         */
    459         size_t n_set(void) const
    460         {       return n_set_; }
    461         // -----------------------------------------------------------------
    462         /*! Fetch end for this vector of sets object.
    463 
    464         \return
    465         is the maximum element value plus one (the minimum element value is 0).
    466         */
    467         size_t end(void) const
    468         {       return end_; }
    469827};
    470828// Tell pod_vector class that each pair_size_t is plain old data and hence
  • trunk/doc.omh

    r3790 r3791  
    9292$comment bin/version assumes that : follows cppad version number here$$
    9393$section
    94 cppad-20160220: A Package for Differentiation of C++ Algorithms
     94cppad-20160223: A Package for Differentiation of C++ Algorithms
    9595$$
    9696$mindex AD algorithmic differentiation automatic C++ algorithm derivative CppAD version cppad.hpp$$
  • trunk/omh/install/download.omh

    r3790 r3791  
    9797$rnext
    9898current  $cnext EPL $cnext $href%
    99 http://www.coin-or.org/download/source/CppAD/cppad-20160220.epl.tgz%
    100 cppad-20160220.epl.tgz%$$
     99http://www.coin-or.org/download/source/CppAD/cppad-20160223.epl.tgz%
     100cppad-20160223.epl.tgz%$$
    101101$rnext
    102102current  $cnext GPL $cnext $href%
    103 http://www.coin-or.org/download/source/CppAD/cppad-20160220.gpl.tgz%
    104 cppad-20160220.gpl.tgz%$$
     103http://www.coin-or.org/download/source/CppAD/cppad-20160223.gpl.tgz%
     104cppad-20160223.gpl.tgz%$$
    105105$tend
    106106
  • trunk/omh/whats_new/whats_new_16.omh

    r3784 r3791  
    2222        std
    2323        namespace
     24        cppad
    2425$$
    2526
     
    3132The purpose of these sections is to
    3233assist you in learning about changes between various versions of CppAD.
     34
     35$head 02-23$$
     36A new version of the
     37$cref/cppad_sparse_list/cmake/cppad_sparse_list/$$ class uses
     38reference counters reduce the number of copies of sets that are equal.
     39This improved the speed of sparsity pattern computations that use
     40the $cref/vector of sets/glossary/Sparsity Pattern/Vector of Sets/$$
     41representation.
     42For example, the results for the
     43$cref cppad_sparse_hessian.cpp$$ test compare as follows:
     44$codep
     45        sparse_hessian_size     = [  100,    400,   900,  1600, 2500 ]
     46        sparse_hessian_rate_old = [ 1480, 265.21, 93.33, 41.93, 0.86 ]
     47        sparse_hessian_rate_new = [ 1328, 241.61, 92.99, 40.51, 3.80 ]
     48$$
     49Note that the improvement is better for larger problems. In fact,
     50for large problems, the new vector of sets representation preforms better than
     51the $cref/vector of boolean/glossary/Sparsity Pattern/Vector of Boolean/$$
     52representation.
     53
    3354
    3455$head 01-21$$
  • trunk/speed/main.cpp

    r3757 r3791  
    11// $Id$
    22/* --------------------------------------------------------------------------
    3 CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-15 Bradley M. Bell
     3CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-16 Bradley M. Bell
    44
    55CppAD is distributed under multiple licenses. This distribution is under
     
    549549                size_ode[i]         = 10 * i + 1;
    550550                size_poly[i]        = 10 * i + 1;
    551                 size_sparse_hessian[i]  = 100 * (i + 1) * (i + 1);
    552                 size_sparse_jacobian[i] = 100 * (i + 1) * (i + 1);
     551                size_sparse_hessian[i]  = 150 * (i + 1) * (i + 1);
     552                size_sparse_jacobian[i] = 150 * (i + 1) * (i + 1);
    553553        }
    554554
  • trunk/test_more/CMakeLists.txt

    r3788 r3791  
    155155        vec_unary.cpp
    156156        zdouble.cpp
     157
     158        local/vector_set.cpp
    157159)
    158160
  • trunk/test_more/test_more.cpp

    r3768 r3791  
    11// $Id$
    22/* --------------------------------------------------------------------------
    3 CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-15 Bradley M. Bell
     3CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-16 Bradley M. Bell
    44
    55CppAD is distributed under multiple licenses. This distribution is under
     
    117117extern bool zdouble(void);
    118118
     119// tests in local subdirectory
     120extern bool vector_set(void);
     121
    119122namespace {
    120123        // function that runs one test
     
    258261# endif
    259262
     263        // local sub-directory
     264        ok &= Run( test_vector,      "test_vector"   );
     265
    260266        // check for errors
    261267        using std::cout;
Note: See TracChangeset for help on using the changeset viewer.