Re: MTL slow on large matrices?
"Yaron Kretchmer" <[email protected]> Tue, 3 Apr 2007 10:05:17 -0700
| Newsgroups | gmane.comp.lib.mtl.devel |
|---|---|
| Message-ID | <D500AB0F5C034F48AB08127D359BEA1FDC1244@sj-ismsg01.altera.priv.altera.com> |
This is a multi-part message in MIME format. --===============0641338697== Content-class: urn:content-classes:message Content-Type: multipart/alternative; boundary="----_=_NextPart_001_01C77612.40E1E130" This is a multi-part message in MIME format. ------_=_NextPart_001_01C77612.40E1E130 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Thanks for the update Peter It seems that preallocation is a large part of the problem- Petsc becomes very slow too if you don't preallocate. Maybe a quick fix/hack would be to enable preallocation (a-la STL "reserve") in the current code- Is that posible? =20 Yaron ________________________________ From: [email protected] [mailto:[email protected]] On Behalf Of Peter Gottschling Sent: Tuesday, April 03, 2007 9:07 AM To: General Matrix Template Library (MTL) list Subject: Re: MTL: MTL slow on large matrices? Sorry about that Yaron,=20 This is a known problem with MTL2 that the performance on large sparse matrices is critical. Preallocation might speed up the construction somehow but wouldn't solve completely. I'm working on a new version of MTL, which I plan to prerelease in the next weeks. It won't have the complete functionality of MTL2 but the matrix insertion will be clearly faster (maybe faster then PETSc ;-) ). It's a completely different implementation. I'll let you know. =20 Cheers, Peter On Apr 3, 2007, at 11:29 AM, Yaron Kretchmer wrote: Hi There. I'm trying to construct a large (4e6 * 1e6) sparse matrix, with nnz per row/column at <10. MTL gives really horrible performance compared to other sparse matrix libraries (Such as Petsc)- I'm talking about just the construction of the matrix itself, no arithmetic operations. In tests I've conducted the difference is about 30X. I'm suspecting this is because MTL does not preallocate sparse matrix memory. but rather enlarges the underlying STL objects as new values are put into the matrix- does that make sense? =09 Is there a way of enforcing preallocation (preferably individually at a per-row/per-column basis, but even globally would be a good place to start) when creating sparse matrix objects? =09 Cheers Yaron=20 _______________________________________________ This list is archived at http://www.osl.iu.edu/MailArchives/mtl-devel/ ------------ Peter Gottschling Research Associate Open Systems Laboratory Indiana University 135 Lindley Hall Bloomington, IN 47405 Tel.: +1 812 855-3608 Fax: +1 812 856 0853 http://www.osl.iu.edu/~pgottsch ------_=_NextPart_001_01C77612.40E1E130 Content-Type: text/html; charset="us-ascii" Content-Transfer-Encoding: quoted-printable <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML><HEAD> <META http-equiv=3DContent-Type content=3D"text/html; = charset=3Dus-ascii"> <META content=3D"MSHTML 6.00.3790.2817" name=3DGENERATOR></HEAD> <BODY=20 style=3D"WORD-WRAP: break-word; khtml-nbsp-mode: space; = khtml-line-break: after-white-space"> <DIV dir=3Dltr align=3Dleft><SPAN class=3D296090417-03042007><FONT = face=3DArial=20 color=3D#0000ff size=3D2>Thanks for the update Peter</FONT></SPAN></DIV> <DIV dir=3Dltr align=3Dleft><SPAN class=3D296090417-03042007><FONT = face=3DArial=20 color=3D#0000ff size=3D2>It seems that preallocation is a large part of = the problem-=20 Petsc becomes very slow too if you don't preallocate. Maybe a quick = fix/hack=20 would be to enable preallocation (a-la STL "reserve") in the current = code- Is=20 that posible?</FONT></SPAN></DIV> <DIV dir=3Dltr align=3Dleft><SPAN class=3D296090417-03042007><FONT = face=3DArial=20 color=3D#0000ff size=3D2></FONT></SPAN> </DIV> <DIV dir=3Dltr align=3Dleft><SPAN class=3D296090417-03042007><FONT = face=3DArial=20 color=3D#0000ff size=3D2>Yaron</FONT></SPAN></DIV><BR> <DIV class=3DOutlookMessageHeader lang=3Den-us dir=3Dltr align=3Dleft> <HR tabIndex=3D-1> <FONT face=3DTahoma size=3D2><B>From:</B> [email protected]=20 [mailto:[email protected]] <B>On Behalf Of </B>Peter=20 Gottschling<BR><B>Sent:</B> Tuesday, April 03, 2007 9:07 = AM<BR><B>To:</B>=20 General Matrix Template Library (MTL) list<BR><B>Subject:</B> Re: MTL: = MTL slow=20 on large matrices?<BR></FONT><BR></DIV> <DIV></DIV>Sorry about that Yaron, <DIV><BR class=3Dkhtml-block-placeholder></DIV> <DIV>This is a known problem with MTL2 that the performance on large = sparse=20 matrices is critical. Preallocation might speed up the = construction=20 somehow but wouldn't solve completely.</DIV> <DIV><BR class=3Dkhtml-block-placeholder></DIV> <DIV>I'm working on a new version of MTL, which I plan to prerelease in = the next=20 weeks. It won't have the complete functionality of MTL2 but the = matrix=20 insertion will be clearly faster (maybe faster then PETSc ;-) ). = It's a=20 completely different implementation. I'll let you know.</DIV> <DIV> </DIV> <DIV>Cheers,</DIV> <DIV>Peter</DIV> <DIV><BR> <DIV> <DIV>On Apr 3, 2007, at 11:29 AM, Yaron Kretchmer wrote:</DIV><BR=20 class=3DApple-interchange-newline> <BLOCKQUOTE type=3D"cite"> <P><FONT size=3D2>Hi There.<BR>I'm trying to construct a large (4e6 * = 1e6)=20 sparse matrix, with nnz per row/column at <10.<BR>MTL gives really = horrible=20 performance compared to other sparse matrix libraries (Such as Petsc)- = I'm=20 talking about just the construction of the matrix itself, no = arithmetic=20 operations. In tests I've conducted the difference is about = 30X.<BR>I'm=20 suspecting this is because MTL does not preallocate sparse matrix = memory. but=20 rather enlarges the underlying STL objects as new values are put into = the=20 matrix- does that make sense?<BR><BR>Is there a way of enforcing = preallocation=20 (preferably individually at a per-row/per-column basis, but even = globally=20 would be a good place to start) when creating sparse matrix=20 objects?<BR><BR>Cheers<BR>Yaron</FONT> </P> <DIV style=3D"MARGIN: = 0px">_______________________________________________</DIV> <DIV style=3D"MARGIN: 0px">This list is archived at <A=20 = href=3D"http://www.osl.iu.edu/MailArchives/mtl-devel/">http://www.osl.iu.= edu/MailArchives/mtl-devel/</A></DIV></BLOCKQUOTE></DIV><BR> <DIV><SPAN class=3DApple-style-span=20 style=3D"WORD-SPACING: 0px; FONT: 12px Helvetica; TEXT-TRANSFORM: none; = COLOR: rgb(0,0,0); TEXT-INDENT: 0px; WHITE-SPACE: normal; = LETTER-SPACING: normal; BORDER-COLLAPSE: separate; border-spacing: 0px = 0px; khtml-text-decorations-in-effect: none; apple-text-size-adjust: = auto; orphans: 2; widows: 2"><SPAN=20 class=3DApple-style-span=20 style=3D"WORD-SPACING: 0px; FONT: 12px Helvetica; TEXT-TRANSFORM: none; = COLOR: rgb(0,0,0); TEXT-INDENT: 0px; WHITE-SPACE: normal; = LETTER-SPACING: normal; BORDER-COLLAPSE: separate; border-spacing: 0px = 0px; khtml-text-decorations-in-effect: none; apple-text-size-adjust: = auto; orphans: 2; widows: 2"> <DIV>------------</DIV> <DIV>Peter Gottschling</DIV> <DIV>Research Associate</DIV> <DIV>Open Systems Laboratory</DIV> <DIV>Indiana University</DIV> <DIV>135 Lindley Hall</DIV> <DIV>Bloomington, IN 47405</DIV> <DIV>Tel.: +1 812 855-3608 Fax: +1 812 856 0853</DIV> <DIV><A=20 href=3D"http://www.osl.iu.edu/~pgottsch">http://www.osl.iu.edu/~pgottsch<= /A></DIV><BR=20 class=3DApple-interchange-newline></SPAN></SPAN></DIV><BR></DIV></BODY></= HTML> ------_=_NextPart_001_01C77612.40E1E130-- --===============0641338697== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline _______________________________________________ This list is archived at http://www.osl.iu.edu/MailArchives/mtl-devel/ --===============0641338697==--