Mercurial > hg > octave-lyh
changeset 8651:ea8e65ca234f
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 +++ b/liboctave/Array-d.cc @@ -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 +++ b/liboctave/Array-f.cc @@ -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 +++ b/liboctave/Array.cc @@ -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 +++ b/liboctave/Array.h @@ -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 +++ b/liboctave/ChangeLog @@ -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 +++ b/src/ChangeLog @@ -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 +++ b/src/TEMPLATE-INST/Array-tc.cc @@ -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);