From c13310dc3fc3c312c7a71be1b2918d4670c45a1a Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Sun, 18 Mar 2012 21:40:49 -0700 Subject: [PATCH] sort: Allocate space for sort buffers on demand, not in advance. Each call to sort_create_writer() was allocating possibly a very large amount of memory when in many cases only a small fraction of that memory would actually be used. This commit switches to allocating a small amount of memory and gradually increasing the allocation on demand. Reported by John Darrington. Bug #35887. --- src/math/sort.c | 33 +++++++++++++++++++++++---------- 1 file changed, 23 insertions(+), 10 deletions(-) diff --git a/src/math/sort.c b/src/math/sort.c index 3491a20bfd..a780d49c6b 100644 --- a/src/math/sort.c +++ b/src/math/sort.c @@ -1,5 +1,5 @@ /* PSPP - a program for statistical analysis. - Copyright (C) 1997-9, 2000, 2006, 2009, 2011 Free Software Foundation, Inc. + Copyright (C) 1997-9, 2000, 2006, 2009, 2011, 2012 Free Software Foundation, Inc. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -200,8 +200,9 @@ struct pqueue { struct subcase ordering; struct pqueue_record *records; - size_t record_cnt; - size_t record_cap; + size_t record_cnt; /* Current number of records. */ + size_t record_cap; /* Space currently allocated for records. */ + size_t record_max; /* Max space we are willing to allocate. */ casenumber idx; }; @@ -222,13 +223,14 @@ pqueue_create (const struct subcase *ordering, const struct caseproto *proto) pq = xmalloc (sizeof *pq); subcase_clone (&pq->ordering, ordering); - pq->record_cap = settings_get_workspace_cases (proto); - if (pq->record_cap > max_buffers) - pq->record_cap = max_buffers; - else if (pq->record_cap < min_buffers) - pq->record_cap = min_buffers; + pq->record_max = settings_get_workspace_cases (proto); + if (pq->record_max > max_buffers) + pq->record_max = max_buffers; + else if (pq->record_max < min_buffers) + pq->record_max = min_buffers; pq->record_cnt = 0; - pq->records = xnmalloc (pq->record_cap, sizeof *pq->records); + pq->record_cap = 0; + pq->records = NULL; pq->idx = 0; return pq; @@ -254,7 +256,7 @@ pqueue_destroy (struct pqueue *pq) static bool pqueue_is_full (const struct pqueue *pq) { - return pq->record_cnt >= pq->record_cap; + return pq->record_cnt >= pq->record_max; } static bool @@ -270,6 +272,17 @@ pqueue_push (struct pqueue *pq, struct ccase *c, casenumber id) assert (!pqueue_is_full (pq)); + if (pq->record_cnt >= pq->record_cap) + { + pq->record_cap = pq->record_cap * 2; + if (pq->record_cap < 16) + pq->record_cap = 16; + else if (pq->record_cap > pq->record_max) + pq->record_cap = pq->record_max; + pq->records = xrealloc (pq->records, + pq->record_cap * sizeof *pq->records); + } + r = &pq->records[pq->record_cnt++]; r->id = id; r->c = c; -- 2.30.2