Mercurial > octave-nkf

changeset 8651:ea8e65ca234f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
reduce memory usage in sorting
author Jaroslav Hajek <highegg@gmail.com>
date Tue, 03 Feb 2009 08:16:39 +0100
parents a1ae2aae903e
children b93f17317ca3
files liboctave/Array-d.cc liboctave/Array-f.cc liboctave/Array.cc liboctave/Array.h liboctave/ChangeLog src/ChangeLog src/TEMPLATE-INST/Array-tc.cc
diffstat 7 files changed, 107 insertions(+), 81 deletions(-) [+]
line wrap: on
line diff
--- a/liboctave/Array-d.cc	Mon Feb 02 15:35:32 2009 +0100
+++ b/liboctave/Array-d.cc	Tue Feb 03 08:16:39 2009 +0100
@@ -60,9 +60,9 @@
 
 template <>
 bool
-ascending_compare (vec_index<double> *a, vec_index<double> *b)
+ascending_compare (const double *a, const double *b)
 {
-  return (xisnan (b->vec) || (a->vec < b->vec));
+  return (xisnan (*b) || (*a < *b));
 }
 
 template <>
@@ -74,9 +74,9 @@
 
 template <>
 bool
-descending_compare (vec_index<double> *a, vec_index<double> *b)
+descending_compare (const double *a, const double *b)
 {
-  return (xisnan (b->vec) || (a->vec > b->vec));
+  return (xisnan (*b) || (*a > *b));
 }
 
 INSTANTIATE_ARRAY_SORT (uint64_t);
@@ -85,7 +85,7 @@
 Array<double>
 Array<double>::sort (octave_idx_type dim, sortmode mode) const
 {
-  Array<double> m = *this;
+  Array<double> m (dims ());
 
   dim_vector dv = m.dims ();
 
@@ -99,8 +99,10 @@
     stride *= dv(i);
 
   double *v = m.fortran_vec ();
+  const double *ov = data ();
 
   uint64_t *p = reinterpret_cast<uint64_t *> (v);
+  const uint64_t *op = reinterpret_cast<const uint64_t *> (ov);
 
   octave_sort<uint64_t> lsort;
 
@@ -119,7 +121,7 @@
 	  // IEEE754 give the correct ordering.
 
 	  for (octave_idx_type i = 0; i < ns; i++)
-	    p[i] = FloatFlip (p[i]);
+	    p[i] = FloatFlip (op[i]);
 	      
 	  lsort.sort (p, ns);
 
@@ -161,6 +163,7 @@
 	    }
 
 	  p += ns;
+          op += ns;
 	}
     }
   else
@@ -182,7 +185,7 @@
 	  // IEEE754 give the correct ordering.
 
 	  for (octave_idx_type i = 0; i < ns; i++)
-	    vi[i] = FloatFlip (p[i*stride + offset]);
+	    vi[i] = FloatFlip (op[i*stride + offset]);
 
 	  lsort.sort (vi, ns);
 
@@ -231,7 +234,7 @@
 Array<double>::sort (Array<octave_idx_type> &sidx, octave_idx_type dim, 
 		     sortmode mode) const
 {
-  Array<double> m = *this;
+  Array<double> m (dims ());
 
   dim_vector dv = m.dims ();
 
@@ -248,10 +251,12 @@
     stride *= dv(i);
 
   double *v = m.fortran_vec ();
+  const double *ov = data ();
 
   uint64_t *p = reinterpret_cast<uint64_t *> (v);
+  const uint64_t *op = reinterpret_cast<const uint64_t *> (ov);
 
-  octave_sort<vec_index<uint64_t> *> indexed_sort;
+  octave_sort<const uint64_t *> indexed_sort;
 
   if (mode == ASCENDING)
     indexed_sort.set_compare (ascending_compare);
@@ -260,12 +265,9 @@
   else
     abort ();
 
-  OCTAVE_LOCAL_BUFFER (vec_index<uint64_t> *, vi, ns);
-  OCTAVE_LOCAL_BUFFER (vec_index<uint64_t>, vix, ns);
+  OCTAVE_LOCAL_BUFFER (const uint64_t *, vi, ns);
+  OCTAVE_LOCAL_BUFFER (uint64_t, vix, ns);
   
-  for (octave_idx_type i = 0; i < ns; i++)
-    vi[i] = &vix[i];
-
   sidx = Array<octave_idx_type> (dv);
       
   for (octave_idx_type j = 0; j < iter; j++)
@@ -284,8 +286,8 @@
 
       for (octave_idx_type i = 0; i < ns; i++)
 	{
-	  vi[i]->vec = FloatFlip (p[i*stride + offset]);
-	  vi[i]->indx = i;
+	  vix[i] = FloatFlip (op[i*stride + offset]);
+	  vi[i] = vix + i;
 	}
 
       indexed_sort.sort (vi, ns);
@@ -295,8 +297,8 @@
 
       for (octave_idx_type i = 0; i < ns; i++)
 	{
-	  p[i*stride + offset] = IFloatFlip (vi[i]->vec);
-	  sidx(i*stride + offset) = vi[i]->indx;
+	  p[i*stride + offset] = IFloatFlip (*vi[i]);
+	  sidx(i*stride + offset) = vi[i] - vix;
 	}
 
       // There are two representations of NaN.  One will be sorted
@@ -362,10 +364,10 @@
 
 template <>
 bool
-ascending_compare (vec_index<double> *a, 
-		   vec_index<double> *b)
+ascending_compare (const double *a, 
+		   const double *b)
 {
-  return (xisnan (b->vec) || (a->vec < b->vec));
+  return (xisnan (*b) || (*a < *b));
 }
 
 template <>
@@ -377,10 +379,10 @@
 
 template <>
 bool
-descending_compare (vec_index<double> *a, 
-		    vec_index<double> *b)
+descending_compare (const double *a, 
+		    const double *b)
 {
-  return (xisnan (b->vec) || (a->vec > b->vec));
+  return (xisnan (*b) || (*a > *b));
 }
 
 INSTANTIATE_ARRAY_SORT (double);
--- a/liboctave/Array-f.cc	Mon Feb 02 15:35:32 2009 +0100
+++ b/liboctave/Array-f.cc	Tue Feb 03 08:16:39 2009 +0100
@@ -60,9 +60,9 @@
 
 template <>
 bool
-ascending_compare (vec_index<float> *a, vec_index<float> *b)
+ascending_compare (const float *a, const float *b)
 {
-  return (xisnan (b->vec) || (a->vec < b->vec));
+  return (xisnan (*b) || (*a < *b));
 }
 
 template <>
@@ -74,9 +74,9 @@
 
 template <>
 bool
-descending_compare (vec_index<float> *a, vec_index<float> *b)
+descending_compare (const float *a, const float *b)
 {
-  return (xisnan (b->vec) || (a->vec > b->vec));
+  return (xisnan (*b) || (*a > *b));
 }
 
 INSTANTIATE_ARRAY_SORT (uint32_t);
@@ -85,7 +85,7 @@
 Array<float>
 Array<float>::sort (octave_idx_type dim, sortmode mode) const
 {
-  Array<float> m = *this;
+  Array<float> m (dims ());
 
   dim_vector dv = m.dims ();
 
@@ -99,8 +99,10 @@
     stride *= dv(i);
 
   float *v = m.fortran_vec ();
+  const float *ov = data ();
 
   uint32_t *p = reinterpret_cast<uint32_t *> (v);
+  const uint32_t *op = reinterpret_cast<const uint32_t *> (ov);
 
   octave_sort<uint32_t> lsort;
 
@@ -119,7 +121,7 @@
 	  // IEEE754 give the correct ordering.
 
 	  for (octave_idx_type i = 0; i < ns; i++)
-	    p[i] = FloatFlip (p[i]);
+	    p[i] = FloatFlip (op[i]);
 	      
 	  lsort.sort (p, ns);
 
@@ -161,6 +163,7 @@
 	    }
 
 	  p += ns;
+          op += ns;
 	}
     }
   else
@@ -182,7 +185,7 @@
 	  // IEEE754 give the correct ordering.
 
 	  for (octave_idx_type i = 0; i < ns; i++)
-	    vi[i] = FloatFlip (p[i*stride + offset]);
+	    vi[i] = FloatFlip (op[i*stride + offset]);
 
 	  lsort.sort (vi, ns);
 
@@ -231,7 +234,7 @@
 Array<float>::sort (Array<octave_idx_type> &sidx, octave_idx_type dim, 
 		     sortmode mode) const
 {
-  Array<float> m = *this;
+  Array<float> m (dims ());
 
   dim_vector dv = m.dims ();
 
@@ -248,10 +251,12 @@
     stride *= dv(i);
 
   float *v = m.fortran_vec ();
+  const float *ov = data ();
 
   uint32_t *p = reinterpret_cast<uint32_t *> (v);
+  const uint32_t *op = reinterpret_cast<const uint32_t *> (ov);
 
-  octave_sort<vec_index<uint32_t> *> indexed_sort;
+  octave_sort<const uint32_t *> indexed_sort;
 
   if (mode == ASCENDING)
     indexed_sort.set_compare (ascending_compare);
@@ -260,12 +265,9 @@
   else
     abort ();
 
-  OCTAVE_LOCAL_BUFFER (vec_index<uint32_t> *, vi, ns);
-  OCTAVE_LOCAL_BUFFER (vec_index<uint32_t>, vix, ns);
+  OCTAVE_LOCAL_BUFFER (const uint32_t *, vi, ns);
+  OCTAVE_LOCAL_BUFFER (uint32_t, vix, ns);
   
-  for (octave_idx_type i = 0; i < ns; i++)
-    vi[i] = &vix[i];
-
   sidx = Array<octave_idx_type> (dv);
       
   for (octave_idx_type j = 0; j < iter; j++)
@@ -284,8 +286,8 @@
 
       for (octave_idx_type i = 0; i < ns; i++)
 	{
-	  vi[i]->vec = FloatFlip (p[i*stride + offset]);
-	  vi[i]->indx = i;
+	  vix[i] = FloatFlip (op[i*stride + offset]);
+	  vi[i] = vix + i;
 	}
 
       indexed_sort.sort (vi, ns);
@@ -295,8 +297,8 @@
 
       for (octave_idx_type i = 0; i < ns; i++)
 	{
-	  p[i*stride + offset] = IFloatFlip (vi[i]->vec);
-	  sidx(i*stride + offset) = vi[i]->indx;
+	  p[i*stride + offset] = IFloatFlip (*vi[i]);
+	  sidx(i*stride + offset) = vi[i] - vix;
 	}
 
       // There are two representations of NaN.  One will be sorted
@@ -362,10 +364,10 @@
 
 template <>
 bool
-ascending_compare (vec_index<float> *a, 
-		   vec_index<float> *b)
+ascending_compare (const float *a, 
+		   const float *b)
 {
-  return (xisnan (b->vec) || (a->vec < b->vec));
+  return (xisnan (*b) || (*a < *b));
 }
 
 template <>
@@ -377,10 +379,10 @@
 
 template <>
 bool
-descending_compare (vec_index<float> *a, 
-		    vec_index<float> *b)
+descending_compare (const float *a, 
+		    const float *b)
 {
-  return (xisnan (b->vec) || (a->vec > b->vec));
+  return (xisnan (*b) || (*a > *b));
 }
 
 INSTANTIATE_ARRAY_SORT (float);
--- a/liboctave/Array.cc	Mon Feb 02 15:35:32 2009 +0100
+++ b/liboctave/Array.cc	Tue Feb 03 08:16:39 2009 +0100
@@ -1991,23 +1991,23 @@
 
 template <class T>
 bool 
-ascending_compare (vec_index<T> *a, vec_index<T> *b)
+ascending_compare (const T *a, const T *b)
 {
-  return (a->vec < b->vec);
+  return (*a < *b);
 }
 
 template <class T>
 bool 
-descending_compare (vec_index<T> *a, vec_index<T> *b)
+descending_compare (const T *a, const T *b)
 {
-  return (a->vec > b->vec);
+  return (*a > *b);
 }
 
 template <class T>
 Array<T>
 Array<T>::sort (octave_idx_type dim, sortmode mode) const
 {
-  Array<T> m = *this;
+  Array<T> m (dims ());
 
   dim_vector dv = m.dims ();
 
@@ -2022,6 +2022,8 @@
     stride *= dv(i);
 
   T *v = m.fortran_vec ();
+  const T *ov = data ();
+
   octave_sort<T> lsort;
   
   if (mode == ASCENDING) 
@@ -2035,8 +2037,10 @@
     {
       for (octave_idx_type j = 0; j < iter; j++)
 	{
+          std::copy (ov, ov + ns, v);
 	  lsort.sort (v, ns);
 	  v += ns;
+          ov += ns;
 	}
     }
   else
@@ -2057,7 +2061,7 @@
 	  offset += offset2 * stride * ns;
 	  
 	  for (octave_idx_type i = 0; i < ns; i++)
-	    pvi[i] = v[i*stride + offset];
+	    pvi[i] = ov[i*stride + offset];
 
 	  lsort.sort (pvi, ns);
 	      
@@ -2074,7 +2078,7 @@
 Array<T>::sort (Array<octave_idx_type> &sidx, octave_idx_type dim, 
 		sortmode mode) const
 {
-  Array<T> m = *this;
+  Array<T> m (dims ());
 
   dim_vector dv = m.dims ();
 
@@ -2092,7 +2096,9 @@
     stride *= dv(i);
 
   T *v = m.fortran_vec ();
-  octave_sort<vec_index<T> *> indexed_sort;
+  const T *ov = data ();
+
+  octave_sort<const T *> indexed_sort;
 
   if (mode == ASCENDING) 
     indexed_sort.set_compare (ascending_compare);
@@ -2101,11 +2107,7 @@
   else
     abort ();
 
-  OCTAVE_LOCAL_BUFFER (vec_index<T> *, vi, ns);
-  OCTAVE_LOCAL_BUFFER (vec_index<T>, vix, ns);
-
-  for (octave_idx_type i = 0; i < ns; i++)
-    vi[i] = &vix[i];
+  OCTAVE_LOCAL_BUFFER (const T *, vi, ns);
 
   sidx = Array<octave_idx_type> (dv);
       
@@ -2116,23 +2118,23 @@
 	   octave_idx_type offset = j * ns;
 
 	  for (octave_idx_type i = 0; i < ns; i++)
-	    {
-	      vi[i]->vec = v[i];
-	      vi[i]->indx = i;
-	    }
+            vi[i] = ov + i;
 
 	  indexed_sort.sort (vi, ns);
 
 	  for (octave_idx_type i = 0; i < ns; i++)
 	    {
-	      v[i] = vi[i]->vec;
-	      sidx(i + offset) = vi[i]->indx;
+	      v[i] = *vi[i];
+	      sidx(i + offset) = vi[i] - ov;
 	    }
 	  v += ns;
+          ov += ns;
 	}
     }
   else
     {
+      OCTAVE_LOCAL_BUFFER (T, vix, ns);
+
       for (octave_idx_type j = 0; j < iter; j++)
 	{
 	  octave_idx_type offset = j;
@@ -2148,16 +2150,16 @@
 	      
 	  for (octave_idx_type i = 0; i < ns; i++)
 	    {
-	      vi[i]->vec = v[i*stride + offset];
-	      vi[i]->indx = i;
+	      vix[i] = ov[i*stride + offset];
+	      vi[i] = vix + i;
 	    }
 
 	  indexed_sort.sort (vi, ns);
 	      
 	  for (octave_idx_type i = 0; i < ns; i++)
 	    {
-	      v[i*stride+offset] = vi[i]->vec;
-	      sidx(i*stride+offset) = vi[i]->indx;
+	      v[i*stride+offset] = *vi[i];
+	      sidx(i*stride+offset) = vi[i] - vix;
 	    }
 	}
     }
@@ -2170,11 +2172,11 @@
 template <>
 bool ascending_compare (double, double);
 template <>
-bool ascending_compare (vec_index<double>*, vec_index<double>*);
+bool ascending_compare (const double*, const double*);
 template <>
 bool descending_compare (double, double);
 template <>
-bool descending_compare (vec_index<double>*, vec_index<double>*);
+bool descending_compare (const double*, const double*);
 
 template <>
 Array<double> Array<double>::sort (octave_idx_type dim, sortmode mode) const;
--- a/liboctave/Array.h	Mon Feb 02 15:35:32 2009 +0100
+++ b/liboctave/Array.h	Tue Feb 03 08:16:39 2009 +0100
@@ -594,16 +594,15 @@
 
 #define INSTANTIATE_ARRAY_SORT(T) \
   template class octave_sort<T>; \
-  template class vec_index<T>; \
-  template class octave_sort<vec_index<T> *>;
+  template class octave_sort<const T*>;
 
 #define NO_INSTANTIATE_ARRAY_SORT(T) \
   template class vec_index<T>; \
   template <> bool ascending_compare (T, T) { return true; } \
-  template <> bool ascending_compare (vec_index<T> *, vec_index<T> *) \
+  template <> bool ascending_compare (const T *, const T *) \
     { return true; } \
   template <> bool descending_compare (T, T) { return true; } \
-  template <> bool descending_compare (vec_index<T> *, vec_index<T> *) \
+  template <> bool descending_compare (const T *, const T *) \
     { return true; } \
   template <> Array<T> Array<T>::sort \
     (octave_idx_type, sortmode) const { return *this; } \
--- a/liboctave/ChangeLog	Mon Feb 02 15:35:32 2009 +0100
+++ b/liboctave/ChangeLog	Tue Feb 03 08:16:39 2009 +0100
@@ -1,3 +1,20 @@
+2009-02-03  Jaroslav Hajek  <highegg@gmail.com>
+
+	* Array.cc (Array<T>::sort (octave_idx_type, sortmode)):
+	Copy array on-the-fly.
+	(Array<T>::sort (Array<octave_idx_type> &, octave_idx_type, sortmode)):
+	Copy array on-the-fly, use bare pointers rather than vec_index.
+
+	* Array-d.cc (Array<double>::sort (octave_idx_type, sortmode)):
+	Copy array on-the-fly.
+	(Array<double>::sort (Array<octave_idx_type> &, octave_idx_type, sortmode)):
+	Copy array on-the-fly, use bare pointers rather than vec_index.
+
+	* Array-f.cc (Array<float>::sort (octave_idx_type, sortmode)):
+	Copy array on-the-fly.
+	(Array<float>::sort (Array<octave_idx_type> &, octave_idx_type, sortmode)):
+	Copy array on-the-fly, use bare pointers rather than vec_index.
+
 2009-02-02  Jaroslav Hajek  <highegg@gmail.com>
 
 	* mx-inlines.cc (mx_inline_fabs_dup, mx_inline_cabs_dup): New funcs.
--- a/src/ChangeLog	Mon Feb 02 15:35:32 2009 +0100
+++ b/src/ChangeLog	Tue Feb 03 08:16:39 2009 +0100
@@ -1,3 +1,7 @@
+2009-02-03  Jaroslav Hajek  <highegg@gmail.com>
+
+	* TEMPLATE-INST/Array-tc.cc: Replace vec_index by pointers.
+
 2009-02-02  Jaroslav Hajek  <highegg@gmail.com>
 
 	* ov-re-mat.cc (octave_matrix::abs, octave_matrix::real,
--- a/src/TEMPLATE-INST/Array-tc.cc	Mon Feb 02 15:35:32 2009 +0100
+++ b/src/TEMPLATE-INST/Array-tc.cc	Tue Feb 03 08:16:39 2009 +0100
@@ -53,9 +53,9 @@
 
 template <>
 bool
-ascending_compare (vec_index<octave_value> *a, vec_index<octave_value> *b)
+ascending_compare (const octave_value *a, const octave_value *b)
 {
-  return (a->vec.string_value () < b->vec.string_value ());
+  return (a->string_value () < b->string_value ());
 }
 
 template <>
@@ -67,9 +67,9 @@
 
 template <>
 bool
-descending_compare (vec_index<octave_value> *a, vec_index<octave_value> *b)
+descending_compare (const octave_value *a, const octave_value *b)
 {
-  return (a->vec.string_value () > b->vec.string_value ());
+  return (a->string_value () > b->string_value ());
 }
 
 INSTANTIATE_ARRAY_SORT (octave_value);