Hi everyone,
I am still working on my sparse matrix problem. I would appreciate your help
optimizing the following code. It conses very little (6 conses per
call---not sure where they're coming from), but it is still the bottleneck
in my code. Many of the functions are not being inlined according to Allegro
5.0. (Sorry if the indentation does not come out exactly right in this
message.)
Thanks.
-bruce
[col-index-vec is an adjustable array of hash-tables and contents-vec is an
adjustable array of adjustable arrays]
(defun sparse-matrix-add-val (i
j
val
row-index-table
col-index-vec
contents-vec)
"Places a new value in a sparse matrix data structure."
(declare (type (integer 0 65535) i j val)
(hash-table row-index-table)
(array col-index-vec contents-vec)
#+allegro-v5.0 (:explain :calls :types)
)
(let* ((i-index (the (integer 0 65535)
(gethash i row-index-table)))
(new-table (make-hash-table :test #'eql :size 0)))
(declare (type (integer 0 65535) i-index)
(hash-table new-table))
;; when there's already an entry in row-index-vec for row i
(when i-index
;; add a new column and position to the appropriate subtable of
;; col-index-vec, increment the appropriate element of *num-cols*,
;; and push a new value onto the appropriate subvector of the
;; value vector
(setf (gethash j (aref col-index-vec i-index))
(the (integer 0 65535)
(hash-table-count (aref col-index-vec i-index))))
(vector-push-extend val (aref contents-vec i-index)))
;; when row i is new, add i to row-index-vec
(setf (gethash i row-index-table)
(the (integer 0 65535)
(hash-table-count row-index-table)))
;; put j into a new table at position 0
(setf (gethash j new-table) 0)
;; push the new table onto col-index-vec
(vector-push-extend new-table col-index-vec)
;; push val onto a new vector in contents-vec
(vector-push-extend
(make-array 1
:adjustable t
:fill-pointer 1
:element-type '(integer 0 65535)
:initial-element val)
contents-vec)))
The output of :explain was as follows:
;;; Compiling file sparse-matrix.lisp
;Examining a call to GETHASH with arguments:
; symeval I type (INTEGER 0 65535)
; symeval ROW-INDEX-TABLE type HASH-TABLE
; which returns a value of type (INTEGER 0 65535)
;Generating a non-inline call to GETHASH
;Examining a call to MAKE-HASH-TABLE with arguments:
; constant TEST type SYMBOL
; call to LL type KNOWN-FUNCTION
; constant SIZE type SYMBOL
; constant 0 type (INTEGER 0 0)
; which returns a value of type T
;Examining a call to LL with arguments:
; constant AREF-LONG type SYMBOL
; constant EQL type SYMBOL
; call to LL type T
; which returns a value of type KNOWN-FUNCTION
;Examining a call to LL with arguments:
; constant FIXNUM-TO-MI type SYMBOL
; constant 5 type (INTEGER 5 5)
; which returns a value of type T
;Generating a non-inline call to MAKE-HASH-TABLE
;Examining a call to AREF with arguments:
; symeval COL-INDEX-VEC type (ARRAY * *)
; symeval I-INDEX type (INTEGER 0 65535)
; which returns a value of type T
;Generating a non-inline call to AREF
;Examining a call to HASH-TABLE-COUNT with arguments:
; call to AREF type T
; which returns a value of type (INTEGER 0 65535)
;Examining a call to AREF with arguments:
; symeval COL-INDEX-VEC type (ARRAY * *)
; symeval I-INDEX type (INTEGER 0 65535)
; which returns a value of type T
;Generating a non-inline call to AREF
;Generating a non-inline call to HASH-TABLE-COUNT
;Examining a call to %PUTHASH with arguments:
; symeval G4764 type (INTEGER 0 65535)
; symeval G4765 type T
; symeval G4766 type (INTEGER 0 65535)
; which returns a value of type T
;Generating a non-inline call to %PUTHASH
;Examining a call to VECTOR-PUSH-EXTEND with arguments:
; symeval VAL type (INTEGER 0 65535)
; call to AREF type T
; which returns a value of type T
;Examining a call to AREF with arguments:
; symeval CONTENTS-VEC type (ARRAY * *)
; symeval I-INDEX type (INTEGER 0 65535)
; which returns a value of type T
;Generating a non-inline call to AREF
;Generating a non-inline call to VECTOR-PUSH-EXTEND
;Examining a call to HASH-TABLE-COUNT with arguments:
; symeval ROW-INDEX-TABLE type HASH-TABLE
; which returns a value of type (INTEGER 0 65535)
;Generating a non-inline call to HASH-TABLE-COUNT
;Examining a call to %PUTHASH with arguments:
; symeval G4767 type (INTEGER 0 65535)
; symeval G4768 type HASH-TABLE
; symeval G4769 type (INTEGER 0 65535)
; which returns a value of type T
;Generating a non-inline call to %PUTHASH
;Examining a call to %PUTHASH with arguments:
; symeval G4770 type (INTEGER 0 65535)
; symeval G4771 type HASH-TABLE
; symeval G4772 type (INTEGER 0 0)
; which returns a value of type T
;Generating a non-inline call to %PUTHASH
;Examining a call to VECTOR-PUSH-EXTEND with arguments:
; symeval NEW-TABLE type HASH-TABLE
; symeval COL-INDEX-VEC type (ARRAY * *)
; which returns a value of type T
;Generating a non-inline call to VECTOR-PUSH-EXTEND
;Examining a call to VECTOR-PUSH-EXTEND with arguments:
; call to MAKE-ARRAY type T
; symeval CONTENTS-VEC type (ARRAY * *)
; which returns a value of type T
;Examining a call to MAKE-ARRAY with arguments:
; constant 1 type (INTEGER 1 1)
; constant ADJUSTABLE type SYMBOL
; constant T type SYMBOL
; constant FILL-POINTER type SYMBOL
; constant 1 type (INTEGER 1 1)
; constant ELEMENT-TYPE type SYMBOL
; constant (INTEGER 0 65535) type TRUE-LIST
; constant INITIAL-ELEMENT type SYMBOL
; symeval VAL type (INTEGER 0 65535)
; which returns a value of type T
;Generating a non-inline call to MAKE-ARRAY
;Generating a non-inline NON-SELF tail jump to VECTOR-PUSH-EXTEND
;;; Writing fasl file sparse-matrix.fasl
;;; Fasl write complete
; Fast loading /export/home/bruce/tm-b07-src/sparse-matrix.fasl
--
Bruce L. Lambert
········@uic.edu
From: Robert Monfera
Subject: Re: more help needed on sparse matrices please
Date:
Message-ID: <388B38B6.A05BAC60@fisec.com>
"Bruce L. Lambert" wrote:
> I am still working on my sparse matrix problem. I would appreciate your > help optimizing the following code. It conses very little (6 conses per
> call---not sure where they're coming from), but it is still the
> bottleneck in my code.
I think (setf (gethash ...)) is expected to cons a little if there is a
collision in your hash table. It should not be as much as 6 cells
though, and it should happen on few calls only.
You can declare (integer 0 65535) as (unsigned-byte 16), but the two are
equivalent anyway.
You also call make-array, which definitely conses several bytes (and
probably no cons cells). Is it on purpose that you create a vector and
extend it immediately, whereas you could create a bigger vector and use
(setf (aref ...)) ?.
Robert
From: ······@hotmail.com
Subject: Re: What is Multilinked sparse matrix, implementation?
Date:
Message-ID: <871r68$vbt$1@nnrp1.deja.com>
I designed this progran to implement the sparse matrix. Since I am
working in the confines of the assignment parameters I shall first type
the Assignment:
Write A C program to construct a Multilinked representation of a sparse
matrix. Assume the dimensions as mxn (m rows, n cols). Using the
multilinked representation Add two sparse matricies.
Here is the program I made:
#include<stdio.h>
#include<stdlib.h>
struct list
{
int row, col, data;
struct list *right, *down;
};
void inpval(struct list *h, int m, int n);
void insert(struct list *h, int r, int c, int d);
void display(struct list *h, int n);
void addlist(struct list *ha, struct list *hb, int m, int n);
struct list * gethead(struct list *ha, int i);
void linkarray(struct list *h,int m, int n);
void main()
{
struct list *ha, *hb, *hc;
int m, n, i;
ha = NULL; hb = NULL; hc = NULL;
printf ("\nEnter no. of rows : ");
fflush(stdin); scanf("%d", &m);
printf ("\nEnter no. of cols : ");
fflush(stdin); scanf("%d", &n);
for (i = 0; i < m; i++) ha = gethead(ha, i);
for (i = 0; i < m; i++) hb = gethead(hb, i);
for (i = 0; i < m; i++) hc = gethead(hc, i);
printf ("\nEnter first matrix : ");
inpval(ha,m,n);
inpval(hb,m,n);
display(ha, n);
display(hb, n);
fflush(stdin); getchar();
addlist(ha,hb, m,n);
}
void linkarray(struct list *h,int m, int n)
{
struct list *nextrow, *elefrom, *eleto;
while (h->down != NULL);
{
elefrom = h->right;
while (elefrom->col != -1)
{
while (nextrow->down != NULL)
{
nextrow = h->down;
while (nextrow->col != -1 && eleto->col
!= elefrom->col)
eleto = nextrow->right;
if (nextrow->col != -1) { elefrom->down
= eleto; break; }
}
elefrom = elefrom->right
}
h = h->down;
}
void addlist(struct list *ha, struct list *hb, int m, int n)
{
struct list *M1, *M2;
int i,j,a,b;
ha = ha->right; hb = hb->right;
for(i = 0; i < m; i++)
{
printf ("\n");
for (j = 0; j < n; j++)
{
a = 0;
if (ha->col == j) {a+=ha->data; ha = ha->right;
}
if (hb->col == j) {a+=hb->data; hb = hb->right;
}
printf("%d ", a);
}
ha = ha->down->right; hb = hb->down->right;
}
}
void inpval(struct list *h, int m, int n)
{
int r,c ,d;
printf ("\nEnter values in form of Row, Col, Data");
printf ("\nEntering 0 for row or coloum ends input)");
while(1)
{
printf ("\nEnter Element : ");
scanf("%d,%d,%d", &r, &c, &d);
if (r == 0 || c == 0) break;
if ((r > m) || (c > n)) printf ("\nError, input out of
range!");
else if (d != 0) insert(h, r-1, c-1, d);
}
}
void insert(struct list *h, int r, int c, int d)
{
struct list *rowpoint, *node, *temp, *temp1;
rowpoint = h;
while(rowpoint->row != r) rowpoint = rowpoint->down;
temp1 = rowpoint;
do
{ temp = temp1; temp1 = temp1->right;}
while ((temp1->col < c) && temp1 != rowpoint);
if (temp1->col == c) { temp1->data = d; return; }
node = (struct list *) malloc(sizeof(struct list));
node->data = d; node->col = c; node->row = r; node->down = 0;
node->right = temp->right; temp->right = node;
}
struct list * gethead(struct list *ha, int i)
{
static struct list *tail;
struct list *node;
node = (struct list *) malloc(sizeof(struct list));
node->row = i; node->down = 0; node->col = -1; node->data = 0;
node->right = node;
if (ha == NULL) { tail = node; return(node); }
tail->down = node; tail = node; return (ha);
}
void display(struct list *h, int n)
{
int i,j;
printf("\n");
while (h != NULL)
{
h = h->right;
for (i = 0; i < n; i++)
{
if (i == h->col)
{
printf ("%d ", h->data);
h = h->right;
}
else printf ("0 ");
}
printf ("\n");
h = h->down;
}
}
I hope the program is readable. My matrix is first created by making a
list of header nodes. On accepting the entries (inpval) the elements
are inserted in the appropriate row (using an insertion sort type of
algo, based on the column number).
My questions are as follows :
I have as of mow used the funtion linkarray to provide "down links" for
all the existing nodes. This, as far as adding two matricies is
concerned, is purely cosmetic. The adding function makes no use of the
down pointers. Is there any better way to add two sparse matricies
using the multilink property?
Is there a more efficient way to provide "down" pointers?
Rajeev
Sent via Deja.com http://www.deja.com/
Before you buy.
Centuries ago, Nostradamus foresaw a time when ······@hotmail.com would say:
>I designed this progran to implement the sparse matrix. Since I am
>working in the confines of the assignment parameters I shall first type
>the Assignment:
>Write A C program to construct a Multilinked representation of a sparse
>matrix. Assume the dimensions as mxn (m rows, n cols). Using the
>multilinked representation Add two sparse matricies.
And what, precisely, does this have to do with Lisp?
Are you asking:
a) How to transform this into Lisp?
b) How to use FFI to access these functions from Lisp?
c) How to write the program in Lisp, and then use some sort of code
generator to rewrite it in C?
--
"Ah, fall - when leaves turn to burnished colors upon darkling
branches, collars are turned up against a wind which murmurs of
winter, and homework assignments appear on Usenet. <sigh>"
-- Bob Jarvis
········@ntlug.org- <http://www.hex.net/~cbbrowne/lsf.html>
On Multilinked Sparse Matrices :
1 0 3
consider M = 0 0 4
0 5 6
This can be written as M=(((0,1),(2,3)),((2,4)),((1,5),(2,6)))
This is an ordered sequence of rows.
It is easy to modify the original list to conatain "down pointers"
But I dont think that it is necessary for addition....
Reards
sandeep
Now that it's not 4 a.m., I found an obvious logic bug in my code. It still
needs to be optimized, but at least this one is correct (I think).
-bruce
(defun sparse-matrix-add-val (i
j
val
row-index-table
col-index-vec
contents-vec)
"Places a new value in a sparse matrix data structure."
(declare (type (integer 0 65535) i j val)
(hash-table row-index-table)
(array col-index-vec contents-vec)
(optimize (speed 3) (safety 1) (compilation-time 0))
;;#+allegro-v5.0 (:explain :calls :types)
)
(let* ((i-index (the (integer 0 65535)
(gethash i row-index-table)))
(new-table (make-hash-table :test #'eql :size 0)))
(declare (type (integer 0 65535) i-index)
(hash-table new-table))
;; when there's already an entry in row-index-vec for row i
(if i-index
;; add a new column and position to the appropriate subtable of
;; col-index-vec, increment the appropriate element of *num-cols*,
;; and push a new value onto the appropriate subvector of the
;; value vector
(progn
(setf (gethash j (aref col-index-vec i-index))
(the (integer 0 65535)
(hash-table-count (aref col-index-vec i-index))))
(vector-push-extend val (aref contents-vec i-index)))
;; else
(progn
;; when row i is new, add i to row-index-vec
(setf (gethash i row-index-table)
(the (integer 0 65535)
(hash-table-count row-index-table)))
;; put j into a new table at position 0
(setf (gethash j new-table) 0)
;; push the new table onto col-index-vec
(vector-push-extend new-table col-index-vec)
;; push val onto a new vector in contents-vec
(vector-push-extend
(make-array 1
:adjustable t
:fill-pointer 1
:element-type '(integer 0 65535)
:initial-element val)
contents-vec)))))
Bruce L. Lambert <········@uic.edu> wrote in message
··················@corp.supernews.com...
> Hi everyone,
>
> I am still working on my sparse matrix problem. I would appreciate your
help
> optimizing the following code. It conses very little (6 conses per
> call---not sure where they're coming from), but it is still the bottleneck
> in my code. Many of the functions are not being inlined according to
Allegro
> 5.0. (Sorry if the indentation does not come out exactly right in this
> message.)
>
From: ······@hotmail.com
Subject: What is Multilinked sparse matrix, implementation?
Date:
Message-ID: <86ss0u$ljs$1@nnrp1.deja.com>
Hello,
I'm Computer Science Undergrad in India. I've been asked to
implement a multilinked representation of a Sparse Matrix of M*N
dimensions using C. Is there a set standard for a multilinked
structure. How should I go about doing this?
I've already written a primitive program to do this but it represents
the sparse matrix as a M seperate lists. What is the concept of
multilinking? More then one link per node?
Rajeev
Sent via Deja.com http://www.deja.com/
Before you buy.
From: Robert Monfera
Subject: Re: What is Multilinked sparse matrix, implementation?
Date:
Message-ID: <3891F899.AF2E5169@fisec.com>
Rajeev,
You could have queried the Net. I found this in about 17 seconds (on a
slow 56k modem connection):
http://www.csi.uottawa.ca/~holte/T26/mlinked-lists.html
Why do you have to do it in C, Common Lisp is a better language for
learning concepts like this.
Good luck!
Robert
······@hotmail.com wrote:
>
> Hello,
> I'm Computer Science Undergrad in India. I've been asked to
> implement a multilinked representation of a Sparse Matrix of M*N
> dimensions using C. Is there a set standard for a multilinked
> structure. How should I go about doing this?
>
> I've already written a primitive program to do this but it represents
> the sparse matrix as a M seperate lists. What is the concept of
> multilinking? More then one link per node?
>
> Rajeev
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.