PERF Shrink arrays to size in liblinear helper dense_to_sparse
* expected to be an array of length nrow*ncol.
*
* Typically the matrix will be dense, so we speed up the routine for
- * this case. We create a temporary array temp that collects non-zero
- * elements and after we just memcpy that to the proper array.
+ * this case. We create an array big enough to hold the largest possible
+ * number of non-zero elements and after collecting them we just call
+ * realloc to shrink the array and reclaim any unused memory.
*
* Special care must be taken with indices, since libsvm indices start
* at 1 and not at 0.
@@ -20,20 +21,22 @@ static struct feature_node **dense_to_sparse(double *x, npy_intp *dims,
{
struct feature_node **sparse;
int i, j; /* number of nonzero elements in row i */
- struct feature_node *temp; /* stack for nonzero elements */
struct feature_node *T; /* pointer to the top of the stack */
int count;
sparse = malloc (dims[0] * sizeof(struct feature_node *));
if (sparse == NULL)
- goto sparse_error;
-
- temp = malloc ((dims[1]+2) * sizeof(struct feature_node));
- if (temp == NULL)
- goto temp_error;
+ return NULL;
for (i=0; i<dims[0]; ++i) {
- T = temp; /* reset stack pointer */
+ /* allocate stack for nonzero elements */
+ T = sparse[i] = malloc((dims[1]+2) * sizeof(struct feature_node));
+ if (T == NULL) {
+ for (j=0; j<i-1; j++)
+ free(sparse[j]);
+ free(sparse);
+ return NULL;
+ }
for (j=1; j<=dims[1]; ++j) {
if (*x != 0) {
@@ -55,27 +58,12 @@ static struct feature_node **dense_to_sparse(double *x, npy_intp *dims,
T->index = -1;
++ T;
- /* allocate memory and copy collected items*/
- count = T - temp;
- sparse[i] = malloc(count * sizeof(struct feature_node));
- if (sparse[i] == NULL) {
- int k;
- for (k=0; k<i; k++)
- free(sparse[k]);
- goto sparse_i_error;
- }
- memcpy(sparse[i], temp, count * sizeof(struct feature_node));
+ /* shrink stack to size */
+ count = T - sparse[i];
+ sparse[i] = realloc(sparse[i], count * sizeof(struct feature_node));
}
- free(temp);
return sparse;
-
-sparse_i_error:
- free(temp);
-temp_error:
- free(sparse);
-sparse_error:
- return NULL;
}
