changeset 8523:ad3afaaa19c1

implement non-copying contiguous range indexing
author Jaroslav Hajek <highegg@gmail.com>
date Thu, 15 Jan 2009 07:22:24 +0100
parents d65b33e55d40
children 937921654627
files liboctave/Array.cc liboctave/Array.h liboctave/ChangeLog liboctave/DiagArray2.cc src/ChangeLog src/oct-obj.cc src/oct-obj.h src/ov-base-mat.h src/ov-base.h src/ov-builtin.cc src/ov-cell.cc src/ov-struct.cc src/ov.cc src/ov.h src/pt-decl.h
diffstat 15 files changed, 212 insertions(+), 72 deletions(-) [+]
line wrap: on
line diff
--- a/liboctave/Array.cc
+++ b/liboctave/Array.cc
@@ -3,7 +3,7 @@
 
 Copyright (C) 1993, 1994, 1995, 1996, 1997, 2000, 2002, 2003, 2004,
               2005, 2006, 2007 John W. Eaton 
-Copyright (C) 2008 Jaroslav Hajek <highegg@gmail.com>
+Copyright (C) 2008, 2009 Jaroslav Hajek <highegg@gmail.com>
 
 This file is part of Octave.
 
@@ -47,7 +47,8 @@
 
 template <class T>
 Array<T>::Array (const Array<T>& a, const dim_vector& dv)
-  : rep (a.rep), dimensions (dv)
+  : rep (a.rep), dimensions (dv), 
+    slice_data (a.slice_data), slice_len (a.slice_len)
 {
   rep->count++;
 
@@ -76,6 +77,8 @@
       rep->count++;
 
       dimensions = a.dimensions;
+      slice_data = a.slice_data;
+      slice_len = a.slice_len;
     }
 
   return *this;
@@ -680,6 +683,11 @@
   template <class T>
   void fill (const T& val, T *dest) const { do_fill (val, dest, top); }
 
+  bool is_cont_range (octave_idx_type& l, 
+                            octave_idx_type& u) const
+    {
+      return top == 0 && idx[0].is_cont_range (dim[0], l, u);
+    }
 };
 
 // Helper class for multi-d recursive resizing
@@ -758,9 +766,7 @@
   if (i.is_colon ())
     {
       // A(:) produces a shallow copy as a column vector.
-      retval.dimensions = dim_vector (n, 1);
-      rep->count++;
-      retval.rep = rep;
+      retval = Array<T> (*this, dim_vector (n, 1));
     }
   else if (i.extent (n) != n)
     {
@@ -797,12 +803,19 @@
             rd = dim_vector (1, il);
         }
 
-      // Don't use resize here to avoid useless initialization for POD
-      // types.
-      retval = Array<T> (rd);
+      octave_idx_type l, u;
+      if (il != 0 && i.is_cont_range (n, l, u))
+        // If suitable, produce a shallow slice.
+        retval = Array<T> (*this, rd, l, u);
+      else
+        {
+          // Don't use resize here to avoid useless initialization for POD
+          // types.
+          retval = Array<T> (rd);
 
-      if (il != 0)
-        i.index (data (), n, retval.fortran_vec ());
+          if (il != 0)
+            i.index (data (), n, retval.fortran_vec ());
+        }
     }
 
   return retval;
@@ -830,18 +843,30 @@
     {
       octave_idx_type n = numel (), il = i.length (r), jl = j.length (c);
 
-      // Don't use resize here to avoid useless initialization for POD types.
-      retval = Array<T> (dim_vector (il, jl));
-
       idx_vector ii (i);
 
-      const T* src = data ();
-      T *dest = retval.fortran_vec ();
+      if (ii.maybe_reduce (r, j, c))
+        {
+          octave_idx_type l, u;
+          if (ii.length () > 0 && ii.is_cont_range (n, l, u))
+            // If suitable, produce a shallow slice.
+            retval = Array<T> (*this, dim_vector (il, jl), l, u);
+          else
+            {
+              // Don't use resize here to avoid useless initialization for POD types.
+              retval = Array<T> (dim_vector (il, jl));
 
-      if (ii.maybe_reduce (r, j, c))
-        ii.index (src, n, dest);
+              ii.index (data (), n, retval.fortran_vec ());
+            }
+        }
       else
         {
+          // Don't use resize here to avoid useless initialization for POD types.
+          retval = Array<T> (dim_vector (il, jl));
+
+          const T* src = data ();
+          T *dest = retval.fortran_vec ();
+
           for (octave_idx_type k = 0; k < jl; k++)
             dest += i.index (src + r * j.xelem (k), r, dest);
         }
@@ -898,14 +923,21 @@
           for (int i = 0; i < ial; i++) rdv(i) = ia(i).length (dv(i));
           rdv.chop_trailing_singletons ();
 
-          // Don't use resize here to avoid useless initialization for POD types.
-          retval = Array<T> (rdv);
-
           // Prepare for recursive indexing
           rec_index_helper rh (dv, ia);
 
-          // Do it.
-          rh.index (data (), retval.fortran_vec ());
+          octave_idx_type l, u;
+          if (rh.is_cont_range (l, u))
+            // If suitable, produce a shallow slice.
+            retval = Array<T> (*this, rdv, l, u);
+          else
+            {
+              // Don't use resize here to avoid useless initialization for POD types.
+              retval = Array<T> (rdv);
+
+              // Do it.
+              rh.index (data (), retval.fortran_vec ());
+            }
         }
     }
 
@@ -1842,7 +1874,7 @@
 {
   make_unique ();
 
-  return rep->data;
+  return slice_data;
 }
 
 template <class T>
@@ -2174,10 +2206,12 @@
 void
 Array<T>::print_info (std::ostream& os, const std::string& prefix) const
 {
-  os << prefix << "rep address: " << rep << "\n"
-     << prefix << "rep->len:    " << rep->len << "\n"
-     << prefix << "rep->data:   " << static_cast<void *> (rep->data) << "\n"
-     << prefix << "rep->count:  " << rep->count << "\n";
+  os << prefix << "rep address: " << rep << '\n'
+     << prefix << "rep->len:    " << rep->len << '\n'
+     << prefix << "rep->data:   " << static_cast<void *> (rep->data) << '\n'
+     << prefix << "rep->count:  " << rep->count << '\n'
+     << prefix << "slice_data:  " << static_cast<void *> (slice_data) << '\n'
+     << prefix << "slice_len:   " << slice_len << '\n';
 
   // 2D info:
   //
--- a/liboctave/Array.h
+++ b/liboctave/Array.h
@@ -3,7 +3,7 @@
 
 Copyright (C) 1993, 1994, 1995, 1996, 1997, 2000, 2001, 2002, 2003,
               2004, 2005, 2006, 2007 John W. Eaton
-Copyright (C) 2008 Jaroslav Hajek <highegg@gmail.com>
+Copyright (C) 2008, 2009 Jaroslav Hajek <highegg@gmail.com>
 
 This file is part of Octave.
 
@@ -30,6 +30,7 @@
 #include <cstddef>
 
 #include <iostream>
+#include <algorithm>
 
 #include "dim-vector.h"
 #include "idx-vector.h"
@@ -58,7 +59,12 @@
     octave_idx_type len;
     int count;
 
-    ArrayRep (T *d, octave_idx_type l) : data (d), len (l), count (1) { }
+    ArrayRep (T *d, octave_idx_type l, bool copy = false) 
+      : data (copy ? new T [l] : d), len (l), count (1) 
+        { 
+          if (copy)
+            std::copy (d, d + l, data);
+        }
 
     ArrayRep (void) : data (0), len (0), count (1) { }
 
@@ -67,30 +73,19 @@
     explicit ArrayRep (octave_idx_type n, const T& val)
       : data (new T [n]), len (n), count (1)
       {
-	fill (val);
+        std::fill (data, data + n, val);
       }
 
     ArrayRep (const ArrayRep& a)
       : data (new T [a.len]), len (a.len), count (1)
       {
-        for (octave_idx_type i = 0; i < len; i++)
-	  data[i] = a.data[i];
+        std::copy (a.data, a.data + a.len, data);
       }
  
     ~ArrayRep (void) { delete [] data; }
 
     octave_idx_type length (void) const { return len; }
 
-    void fill (const T& val)
-      {
-	for (octave_idx_type i = 0; i < len; i++)
-	  data[i] = val;
-      }
-
-    T& elem (octave_idx_type n) { return data[n]; }
-
-    T elem (octave_idx_type n) const { return data[n]; }
-
   private:
 
     // No assignment!
@@ -110,19 +105,29 @@
       if (rep->count > 1)
 	{
 	  --rep->count;
-	  rep = new ArrayRep (*rep);
+	  rep = new ArrayRep (slice_data, slice_len, true);
+          slice_data = rep->data;
 	}
-    }
+      else if (slice_len != rep->len)
+        {
+          // Possibly economize here.
+          ArrayRep *new_rep = new ArrayRep (slice_data, slice_len, true);
+          delete rep;
+          rep = new_rep;
+          slice_data = rep->data;
+        }
+      }
 
   void make_unique (const T& val)
     {
       if (rep->count > 1)
 	{
 	  --rep->count;
-	  rep = new ArrayRep (rep->length (), val);
+	  rep = new ArrayRep (slice_len, val);
+          slice_data = rep->data;
 	}
       else
-	rep->fill (val);
+        std::fill (slice_data, slice_data + slice_len, val);
     }
 
   typedef T element_type;
@@ -136,12 +141,33 @@
 
 protected:
 
+  T* slice_data;
+  octave_idx_type slice_len;
+
   Array (T *d, octave_idx_type n)
-    : rep (new typename Array<T>::ArrayRep (d, n)), dimensions (n) { }
+    : rep (new typename Array<T>::ArrayRep (d, n)), dimensions (n) 
+    { 
+      slice_data = rep->data;
+      slice_len = rep->len;
+    }
 
   Array (T *d, const dim_vector& dv)
     : rep (new typename Array<T>::ArrayRep (d, get_size (dv))),
-      dimensions (dv) { }
+      dimensions (dv) 
+    { 
+      slice_data = rep->data;
+      slice_len = rep->len;
+    }
+
+  // slice constructor
+  Array (const Array<T>& a, const dim_vector& dv,
+         octave_idx_type l, octave_idx_type u)
+    : rep(a.rep), dimensions (dv)
+    {
+      rep->count++;
+      slice_data = a.slice_data + l;
+      slice_len = std::min (u, a.slice_len) - l;
+    }
 
 private:
 
@@ -168,14 +194,25 @@
 public:
 
   Array (void)
-    : rep (nil_rep ()), dimensions () { rep->count++; }
+    : rep (nil_rep ()), dimensions () 
+    { 
+      rep->count++; 
+      slice_data = rep->data;
+      slice_len = rep->len;
+    }
 
   explicit Array (octave_idx_type n)
-    : rep (new typename Array<T>::ArrayRep (n)), dimensions (n) { }
+    : rep (new typename Array<T>::ArrayRep (n)), dimensions (n) 
+    { 
+      slice_data = rep->data;
+      slice_len = rep->len;
+    }
 
   explicit Array (octave_idx_type n, const T& val)
     : rep (new typename Array<T>::ArrayRep (n)), dimensions (n)
     {
+      slice_data = rep->data;
+      slice_len = rep->len;
       fill (val);
     }
 
@@ -185,6 +222,8 @@
     : rep (new typename Array<T>::ArrayRep (coerce (a.data (), a.length ()), a.length ())),
       dimensions (a.dimensions)
     {
+      slice_data = rep->data;
+      slice_len = rep->len;
     }
 
   // No type conversion case.
@@ -192,18 +231,26 @@
     : rep (a.rep), dimensions (a.dimensions)
     {
       rep->count++;
+      slice_data = a.slice_data;
+      slice_len = a.slice_len;
     }
 
 public:
 
   Array (const dim_vector& dv)
     : rep (new typename Array<T>::ArrayRep (get_size (dv))),
-      dimensions (dv) { }
+      dimensions (dv) 
+    { 
+      slice_data = rep->data;
+      slice_len = rep->len;
+    }
 
   Array (const dim_vector& dv, const T& val)
     : rep (new typename Array<T>::ArrayRep (get_size (dv))),
       dimensions (dv)
     {
+      slice_data = rep->data;
+      slice_len = rep->len;
       fill (val);
     }
 
@@ -215,7 +262,7 @@
 
   void fill (const T& val) { make_unique (val); }
 
-  octave_idx_type capacity (void) const { return rep->length (); }
+  octave_idx_type capacity (void) const { return slice_len; }
   octave_idx_type length (void) const { return capacity (); }
   octave_idx_type nelem (void) const { return capacity (); }
   octave_idx_type numel (void) const { return nelem (); }
@@ -258,8 +305,8 @@
 
   // No checking, even for multiple references, ever.
 
-  T& xelem (octave_idx_type n) { return rep->elem (n); }
-  T xelem (octave_idx_type n) const { return rep->elem (n); }
+  T& xelem (octave_idx_type n) { return slice_data [n]; }
+  T xelem (octave_idx_type n) const { return slice_data [n]; }
 
   T& xelem (octave_idx_type i, octave_idx_type j) { return xelem (dim1()*j+i); }
   T xelem (octave_idx_type i, octave_idx_type j) const { return xelem (dim1()*j+i); }
@@ -279,7 +326,7 @@
 
   T& checkelem (octave_idx_type n)
     {
-      if (n < 0 || n >= rep->length ())
+      if (n < 0 || n >= slice_len)
 	return range_error ("T& Array<T>::checkelem", n);
       else
 	{
@@ -341,7 +388,7 @@
 
   T checkelem (octave_idx_type n) const
     {
-      if (n < 0 || n >= rep->length ())
+      if (n < 0 || n >= slice_len)
 	return range_error ("T Array<T>::checkelem", n);
       else
 	return xelem (n);
@@ -407,7 +454,7 @@
   Array<T> transpose (void) const;
   Array<T> hermitian (T (*fcn) (const T&) = 0) const;
 
-  const T *data (void) const { return rep->data; }
+  const T *data (void) const { return slice_data; }
 
   const T *fortran_vec (void) const { return data (); }
 
@@ -513,6 +560,17 @@
 
   Array<T>& insert (const Array<T>& a, const Array<octave_idx_type>& idx);
 
+  void maybe_economize (void)
+    {
+      if (rep->count == 1 && slice_len != rep->len)
+        {
+          ArrayRep *new_rep = new ArrayRep (slice_data, slice_len, true);
+          delete rep;
+          rep = new_rep;
+          slice_data = rep->data;
+        }
+    }
+
   void print_info (std::ostream& os, const std::string& prefix) const;
 
   // Unsafe.  This function exists to support the MEX interface.
--- a/liboctave/ChangeLog
+++ b/liboctave/ChangeLog
@@ -1,3 +1,17 @@
+2009-01-14  Jaroslav Hajek  <highegg@gmail.com>
+
+	* Array.cc, Array.h (all Array<T> constructors): Handle slice_data and
+	slice_len.
+	(Array<T>::Array<T> (const Array<T>&, const dim_vector&,
+	octave_idx_type, octave_idx_type)): New constructor.
+	(Array<T>::index): Use shallow copy when index reduces to a contiguous
+	range.
+	(Array<T>::make_unique): Rewrite.
+	(Array<T>::ArrayRep): Delete redundant methods.
+	(rec_index_helper::is_cont_range): New method.
+	(Array<T>::maybe_economize): New method.
+	* DiagArray2.cc (DiagArray2<T>::resize): Fix the mess.
+
 2008-01-15  Rafael Laboissiere  <rafael@debian.org>
 
 	* oct-md5.cc: Include <cstdio>.
--- a/liboctave/DiagArray2.cc
+++ b/liboctave/DiagArray2.cc
@@ -107,6 +107,7 @@
   if (r == dim1 () && c == dim2 ())
     return;
 
+  // FIXME: this is a mess. DiagArray2 really needs a rewrite.
   typename Array<T>::ArrayRep *old_rep = Array<T>::rep;
   const T *old_data = this->data ();
   octave_idx_type old_len = this->length ();
@@ -114,6 +115,8 @@
   octave_idx_type new_len = r < c ? r : c;
 
   Array<T>::rep = new typename Array<T>::ArrayRep (new_len);
+  Array<T>::slice_data = Array<T>::rep->data;
+  Array<T>::slice_len = Array<T>::rep->len;
 
   this->dimensions = dim_vector (r, c);
 
--- a/src/ChangeLog
+++ b/src/ChangeLog
@@ -1,3 +1,18 @@
+2009-01-14  Jaroslav Hajek  <highegg@gmail.com>
+
+	* ov.cc (octave_value::maybe_economize): New method.
+	(octave_value::non_null_value): rename to storable_value.
+	(octave_value::make_non_null_value): rename to make_storable_value.
+	* ov-base.h (octave_base_value::maybe_economize): New method.
+	* ov-base-mat.h (octave_base_mat::maybe_economize): New override.
+	* oct-obj.cc (octave_value_list::normalize_null_values):
+	Rename to make_storable_values, use make_storable_value.
+	* oct-obj.h: Dtto.
+	* ov-builtin.cc: non_null_value -> storable_value.
+	* ov-cell.cc: Dtto.
+	* ov-struct.cc: Dtto.
+	* pt-decl.h: Dtto.
+
 2009-01-15  Søren Hauberg  <hauberg@gmail.com>
 
 	* DLD-FUNCTIONS/__magick_read__.cc (encode_uint_image):
--- a/src/oct-obj.cc
+++ b/src/oct-obj.cc
@@ -236,11 +236,11 @@
 }
 
 void
-octave_value_list::normalize_null_values (void)
+octave_value_list::make_storable_values (void)
 {
   octave_idx_type len = length ();
   for (octave_idx_type i = 0; i < len; i++)
-    data[i].make_non_null_value ();
+    data[i].make_storable_value ();
 }
 
 /*
--- a/src/oct-obj.h
+++ b/src/oct-obj.h
@@ -121,7 +121,7 @@
 
   string_vector name_tags (void) const { return names; }
 
-  void normalize_null_values (void);
+  void make_storable_values (void);
 
 private:
 
--- a/src/ov-base-mat.h
+++ b/src/ov-base-mat.h
@@ -74,6 +74,8 @@
 
   octave_value full_value (void) const { return matrix; }
 
+  void maybe_economize (void) { matrix.maybe_economize (); }
+
   octave_value subsref (const std::string& type,
 			const std::list<octave_value_list>& idx);
 
--- a/src/ov-base.h
+++ b/src/ov-base.h
@@ -152,6 +152,8 @@
 
   virtual octave_base_value *try_narrowing_conversion (void) { return 0; }
 
+  virtual void maybe_economize (void) { }
+
   virtual octave_value
   subsref (const std::string& type,
 	   const std::list<octave_value_list>& idx);
--- a/src/ov-builtin.cc
+++ b/src/ov-builtin.cc
@@ -107,7 +107,7 @@
 	  retval = (*f) (args, nargout);
           // Do not allow null values to be returned from functions.
           // FIXME -- perhaps true builtins should be allowed?
-          retval.normalize_null_values ();
+          retval.make_storable_values ();
 	}
       catch (octave_execution_exception)
 	{
--- a/src/ov-cell.cc
+++ b/src/ov-cell.cc
@@ -270,7 +270,7 @@
 	      }
 	    else if (i.all_scalars () || do_index_op (i, true).numel () == 1)
               // Regularize a null matrix if stored into a cell.
-              octave_base_matrix<Cell>::assign (i, Cell (t_rhs.non_null_value ()));
+              octave_base_matrix<Cell>::assign (i, Cell (t_rhs.storable_value ()));
             else if (! error_state)
               error ("scalar indices required for {} in assignment.");
 
--- a/src/ov-struct.cc
+++ b/src/ov-struct.cc
@@ -412,7 +412,7 @@
 	      }
 	    else
               // Regularize a null matrix if stored into a struct component.
-	      map.assign (key, t_rhs.non_null_value ());
+	      map.assign (key, t_rhs.storable_value ());
 
 	    if (! error_state)
 	      {
--- a/src/ov.cc
+++ b/src/ov.cc
@@ -1170,7 +1170,7 @@
 {
   if (op == op_asn_eq)
     // Regularize a null matrix if stored into a variable.
-    operator = (rhs.non_null_value ());
+    operator = (rhs.storable_value ());
   else
     {
       // FIXME -- only do the following stuff if we can't find
@@ -1552,18 +1552,23 @@
                                              type_name (), "complex vector"));
 }
 
+// FIXME: This is a good place for pre-storage hooks, but the functions should
+// probably be named differently. These functions will be called
 
 octave_value 
-octave_value::non_null_value (void) const
+octave_value::storable_value (void) const
 {
+  octave_value retval = *this;
   if (is_null_value ())
-    return octave_value (rep->empty_clone ());
+    retval = octave_value (rep->empty_clone ());
   else
-    return *this;
+    retval.maybe_economize ();
+
+  return retval;
 }
 
 void 
-octave_value::make_non_null_value (void) 
+octave_value::make_storable_value (void) 
 {
   if (is_null_value ())
     {
@@ -1572,6 +1577,8 @@
         delete rep;
       rep = rc;
     }
+  else
+    maybe_economize ();
 }
 
 int
--- a/src/ov.h
+++ b/src/ov.h
@@ -847,13 +847,18 @@
   Array<FloatComplex> float_complex_vector_value (bool frc_str_conv = false,
 				       bool frc_vec_conv = false) const;
 
-  // Make a copy that is not a special null matrix
+  // Possibly economize a lazy-indexed value.
 
-  octave_value non_null_value (void) const;
+  void maybe_economize (void)
+    { rep->maybe_economize (); }
+
+  // Make a copy suitable for storing.
+
+  octave_value storable_value (void) const;
 
   // Ditto, but in place.
 
-  void make_non_null_value (void);
+  void make_storable_value (void);
 
   // Conversions.  These should probably be private.  If a user of this
   // class wants a certain kind of constant, he should simply ask for
--- a/src/pt-decl.h
+++ b/src/pt-decl.h
@@ -66,7 +66,7 @@
   bool lvalue_ok (void) { return id ? id->lvalue_ok () : false; }
 
   // Do not allow functions return null values
-  octave_value rvalue (void) { return id ? id->rvalue ().non_null_value () : octave_value (); }
+  octave_value rvalue (void) { return id ? id->rvalue ().storable_value () : octave_value (); }
 
   octave_value_list rvalue (int nargout)
   {