From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: ** X-Spam-Status: No, score=2.2 required=5.0 tests=AWL,DNS_FROM_RFC_POST, SPF_NEUTRAL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id EF827BBAF for ; Mon, 23 Feb 2009 23:59:03 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AksCAAO5oknRVcbqlGdsb2JhbACDHol0A4cLPwEBAQEJCwgJEQOyWDGFGIhFAQMBA4QMBoRP X-IronPort-AV: E=Sophos;i="4.38,256,1233529200"; d="scan'208";a="35634247" Received: from rv-out-0506.google.com ([209.85.198.234]) by mail4-smtp-sop.national.inria.fr with ESMTP; 23 Feb 2009 23:59:03 +0100 Received: by rv-out-0506.google.com with SMTP id k40so25131585rvb.57 for ; Mon, 23 Feb 2009 14:59:01 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:sender:received:in-reply-to :references:date:x-google-sender-auth:message-id:subject:from:to:cc :content-type:content-transfer-encoding; bh=TB1QiHat042o8neoh94e8j0aCgbmF50MzpNpY5NeAPc=; b=WqRq8fWsJYpD37QxM0B2qj8xr+BXN1+VAu+wNN9SIqUdpeui4Yt4g8InJPaonljXAt hkZ0AlPZIjAyN4z/y8I8US8oN/JXbvORrElh8O+3u4BkZx9PrOzoiuur5BePEqLTpOog 6gh3hvsmCYgL4OqyLx118pWqYmkaGClvrrLtE= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:sender:in-reply-to:references:date :x-google-sender-auth:message-id:subject:from:to:cc:content-type :content-transfer-encoding; b=OMklIi3y2Xop0rL7eU9DTP6/HjuCyMx9CEpK3VNG1zC4ygne/0U6ywY1eBLPrjuDSu 99tpvGA2RhgfGylsuiIwtebKIyCwEXg6I0Dx6M1bvi9MaaZmJ1fVKHvVrNMJHQT1oEDM k0LmPKUzQZo98QM2LvleF4frgB91vR/r49N7k= MIME-Version: 1.0 Sender: ematsen@gmail.com Received: by 10.141.128.19 with SMTP id f19mr2221192rvn.276.1235429941496; Mon, 23 Feb 2009 14:59:01 -0800 (PST) In-Reply-To: References: <243054520902200740j1d1874adib27645f6e090b073@mail.gmail.com> <499EFA7E.7010400@inria.fr> <243054520902201153q4efbe1f0j686bd7212b515c03@mail.gmail.com> <2a1a1a0c0902201423o5ae7dd3dhb5c64da3c3255a69@mail.gmail.com> Date: Mon, 23 Feb 2009 14:59:01 -0800 X-Google-Sender-Auth: cf6945f6049e174d Message-ID: <243054520902231459t176fb699vd35bdd6fb9401a84@mail.gmail.com> Subject: Re: [Caml-list] speeding up matrix multiplication (newbie question) From: Erick Matsen To: Markus Mottl Cc: "Will M. Farr" , Mike Lin , caml-list@inria.fr Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Spam: no; 0.00; markus:01 mottl:01 rewrote:01 bigarrays:01 lacaml:01 blas:01 lacaml:01 stub:01 stub:01 utils:01 params:01 alloc:01 bigarray:01 markus:01 mottl:01 Hello Caml-community-- First of all, big thanks to Will Farr, Mike Lin, Martin Jambon, and Markus Mottl. So far, I rewrote things in a non-functional way to avoid unecessary memory allocation, and then used the float operations directly. This resulted in a 4 fold increase in speed. Second, I moved some of the code to use Bigarrays and then used the Lacaml BLAS interface. This resulted in another 25% savings. I didn't have big expectations given Markus' email. Indeed, he appears to be right: Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls s/call s/call name 14.90 9.60 9.60 caml_ba_offset 13.82 18.50 8.90 11368070 0.00 0.00 camlFqtree__fun_144 10.35 25.17 6.67 caml_ba_get_N 7.50 30.00 4.83 7456800 0.00 0.00 camlDiagd__fun_309 7.31 34.71 4.71 456351614 0.00 0.00 caml_copy_double 6.85 39.12 4.41 caml_ba_set_aux 5.84 42.88 3.76 880051135 0.00 0.00 caml_c_call 4.43 45.73 2.85 caml_ba_get_1 3.55 48.02 2.29 caml_ba_set_1 1.90 49.24 1.23 __i686.get_pc_thunk.bx 1.89 50.47 1.22 camlVec4_D__of_array_155 1.87 51.67 1.21 lacaml_Zlansy_stub_bc 1.65 52.73 1.06 151152614 0.00 0.00 caml_modify 1.37 53.61 0.88 9788472 0.00 0.00 caml_adjust_gc_speed 1.33 54.47 0.86 12992080 0.00 0.00 camlFqtree__calcLikes_87 0.99 55.11 0.64 caml_ceil_float 0.96 55.73 0.62 lacaml_Dgemv_stub 0.89 56.30 0.57 caml_ba_get_2 0.88 56.88 0.57 camlLacaml_utils__gXmv_get_params_375 0.80 57.39 0.52 caml_ba_dim 0.79 57.90 0.51 camlLacaml4_D__gemv_227 0.78 58.41 0.51 46584 0.00 0.00 sweep_slice 0.76 58.90 0.49 9788472 0.00 0.00 caml_alloc_custom 0.39 59.15 0.25 43714 0.00 0.00 mark_slice 0.39 59.40 0.25 caml_ba_multov As he suggested would be the case, the code is spending most of its time in the bigarray stub function responsible for checking bounds and pulling out the right array element. I wanted to double check that writing my own implementation in fortran or c will eliminate such overhead. Or will I still have to do the "fru-fru" he describes anyway? Again, thank you all. The improvements have already been quite significant. Erick On Fri, Feb 20, 2009 at 2:43 PM, Markus Mottl wrote: > Unless you want to interface C-calls into BLAS/LAPACK directly without > bounds checking, releasing the OCaml-lock, and other "fru-fru", it > seems unlikely that you will get much of an advantage using those > libraries given the small size of your matrices. E.g. Lacaml is > optimized for larger matrices (probably > 10x10). > > I guess you should be fine rolling your own implementation for such > small matrices. > > Regards, > Markus > > -- > Markus Mottl http://www.ocaml.info markus.mottl@gmail.com > > _______________________________________________ > Caml-list mailing list. Subscription management: > http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list > Archives: http://caml.inria.fr > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs >