[Nix-dev] [Nix-commits] [NixOS/nix] 4ccd48: Add a "filter" primop

Mon Aug 13 12:40:45 CEST 2012

Well, I believe the Nix expression language is Turing complete right (although I have no proof), so it is as powerful as any other general purpose language.

Haha!

Just kidding....
________________________________________
From: nix-dev-bounces at lists.science.uu.nl [nix-dev-bounces at lists.science.uu.nl] on behalf of Shea Levy [shea at shealevy.com]
Sent: Monday, August 13, 2012 12:34 PM
To: nix-dev at lists.science.uu.nl; Eelco Dolstra
Cc: nix-commits at lists.science.uu.nl
Subject: Re: [Nix-dev] [Nix-commits] [NixOS/nix] 4ccd48: Add a "filter" primop

If you're not careful, nix may soon be a general purpose language ;)

In seriousness, hooray for optimization!

On Aug 13, 2012, at 2:11 AM, Eelco Dolstra <eelco.dolstra at logicblox.com> wrote:

>  Branch: refs/heads/master
>  Home:   https://github.com/NixOS/nix
>  Commit: 4ccd48ce2478cbe1263605838969f89d5b745f0a
>      https://github.com/NixOS/nix/commit/4ccd48ce2478cbe1263605838969f89d5b745f0a
>  Author: Eelco Dolstra <eelco.dolstra at logicblox.com>
>  Date:   2012-08-12 (Sun, 12 Aug 2012)
>
>  Changed paths:
>    M src/libexpr/eval.cc
>    M src/libexpr/primops.cc
>
>  Log Message:
>  -----------
>  Add a "filter" primop
>
> Evaluation of a NixOS configuration spends quite a lot of time in the
> "filter" function in Nixpkgs.  As implemented in Nixpkgs, this is a
> O(n^2) operation, so it's a good candidate for providing a more
> efficient (i.e. primop) implementation.  Using it gives a ~10% speed
> increase and a significant reduction in the number of evaluations.
>
> Statistics before (on a NixOS system config):
>
>  time elapsed: 1.3258
>  size of a value: 24
>  environments allocated: 1980939 (50127080 bytes)
>  list elements: 14679308 (117434464 bytes)
>  list concatenations: 50828
>  values allocated: 2098938 (50374512 bytes)
>  attribute sets allocated: 392040
>  right-biased unions: 186334
>  values copied in right-biased unions: 591137
>  symbols in symbol table: 18271
>  number of thunks: 1645752
>  number of thunks avoided: 1921196
>  number of attr lookups: 430798
>  number of primop calls: 838807
>  number of function calls: 1930107
>
> Statistics after:
>
>  time elapsed: 1.17982
>  size of a value: 24
>  environments allocated: 1543334 (39624560 bytes)
>  list elements: 9612638 (76901104 bytes)
>  list concatenations: 37434
>  values allocated: 1854933 (44518392 bytes)
>  attribute sets allocated: 392040
>  right-biased unions: 186334
>  values copied in right-biased unions: 591137
>  symbols in symbol table: 18272
>  number of thunks: 1392467
>  number of thunks avoided: 1507311
>  number of attr lookups: 430801
>  number of primop calls: 691600
>  number of function calls: 1492502
>
>
>  Commit: b9e5b908ed29bfb6cd82837f9f57293c1f63e999
>      https://github.com/NixOS/nix/commit/b9e5b908ed29bfb6cd82837f9f57293c1f63e999
>  Author: Eelco Dolstra <eelco.dolstra at logicblox.com>
>  Date:   2012-08-12 (Sun, 12 Aug 2012)
>
>  Changed paths:
>    M src/libexpr/primops.cc
>
>  Log Message:
>  -----------
>  Provide an efficient implementation of ‘elem’
>
> The one in Nixpkgs is O(n^2), this one is O(n).  Big reduction in the
> number of list allocations.
>
> Statistics before (on a NixOS system config):
>
>  time elapsed: 1.17982
>  size of a value: 24
>  environments allocated: 1543334 (39624560 bytes)
>  list elements: 9612638 (76901104 bytes)
>  list concatenations: 37434
>  values allocated: 1854933 (44518392 bytes)
>  attribute sets allocated: 392040
>  right-biased unions: 186334
>  values copied in right-biased unions: 591137
>  symbols in symbol table: 18272
>  number of thunks: 1392467
>  number of thunks avoided: 1507311
>  number of attr lookups: 430801
>  number of primop calls: 691600
>  number of function calls: 1492502
>
> Statistics after:
>
>  time elapsed: 1.08683
>  size of a value: 24
>  environments allocated: 1384376 (35809568 bytes)
>  list elements: 6946783 (55574264 bytes)
>  list concatenations: 37434
>  values allocated: 1760440 (42250560 bytes)
>  attribute sets allocated: 392040
>  right-biased unions: 186334
>  values copied in right-biased unions: 591137
>  symbols in symbol table: 18273
>  number of thunks: 1297673
>  number of thunks avoided: 1380759
>  number of attr lookups: 430802
>  number of primop calls: 628912
>  number of function calls: 1333544
>
>
>  Commit: 198d0338be7c105b6dbd707f98e0c223a8358240
>      https://github.com/NixOS/nix/commit/198d0338be7c105b6dbd707f98e0c223a8358240
>  Author: Eelco Dolstra <eelco.dolstra at logicblox.com>
>  Date:   2012-08-12 (Sun, 12 Aug 2012)
>
>  Changed paths:
>    M src/libexpr/eval.cc
>    M src/libexpr/eval.hh
>    M src/libexpr/primops.cc
>
>  Log Message:
>  -----------
>  Add a primop ‘concatLists’
>
> This can serve as a generic efficient list builder.  For instance, the
> function ‘catAttrs’ in Nixpkgs can be rewritten from
>
>  attr: l: fold (s: l: if hasAttr attr s then [(getAttr attr s)] ++ l else l) [] l
>
> to
>
>  attr: l: builtins.concatLists (map (s: if hasAttr attr s then [(getAttr attr s)] else []) l)
>
> Statistics before:
>
>  time elapsed: 1.08683
>  size of a value: 24
>  environments allocated: 1384376 (35809568 bytes)
>  list elements: 6946783 (55574264 bytes)
>  list concatenations: 37434
>  values allocated: 1760440 (42250560 bytes)
>  attribute sets allocated: 392040
>  right-biased unions: 186334
>  values copied in right-biased unions: 591137
>  symbols in symbol table: 18273
>  number of thunks: 1297673
>  number of thunks avoided: 1380759
>  number of attr lookups: 430802
>  number of primop calls: 628912
>  number of function calls: 1333544
>
> Statistics after (including new catAttrs):
>
>  time elapsed: 0.959854
>  size of a value: 24
>  environments allocated: 1010198 (26829296 bytes)
>  list elements: 1984878 (15879024 bytes)
>  list concatenations: 30488
>  values allocated: 1589760 (38154240 bytes)
>  attribute sets allocated: 392040
>  right-biased unions: 186334
>  values copied in right-biased unions: 591137
>  symbols in symbol table: 18274
>  number of thunks: 1040925
>  number of thunks avoided: 1038428
>  number of attr lookups: 438419
>  number of primop calls: 474844
>  number of function calls: 959366
>
>
> Compare: https://github.com/NixOS/nix/compare/62f72eb9e1a4...198d0338be7c
> _______________________________________________
> nix-commits mailing list
> nix-commits at lists.science.uu.nl
> http://lists.science.uu.nl/mailman/listinfo/nix-commits
_______________________________________________
nix-dev mailing list
nix-dev at lists.science.uu.nl
http://lists.science.uu.nl/mailman/listinfo/nix-dev