4
$\begingroup$

I am writing a large numerical code and I have set up many functions that take several arguments as input. In the functions I am using several built in Mathematica functions, such as Sum[], Part[], ReplacePart[], Select[], FromDigits[], IntegerDigits[] and more. I know in advance that all the input arguments are small integers (or nested lists of small integers), definitely smaller than 100. Also, I do care about numeric performance a lot, so I want to make sure that my functions are as fast as possible. I know about Compile[], but sometimes the compiled version of my functions are outperformed by the non compiled version, and sometimes Compile[] complains about the presence of things like ReplacePart, so I never know in advance whether it is worth to rewrite my functions in a compiled version or not.

My question: Is it numerically faster to specify the argument input types? If yes, how can I do that efficiently avoiding Compile[], which conflicts with ReplacePart[] and other functions? I've tried something like Typed[], but honestly I couldn't see any relevant speed up...

Example: here's a decontextualized example of one function: L, f, sigma, orb are all very small integers, while state is a nested list of small integers. Can I use this information to speed this up?

cdg[L_, f_, \[Sigma]_, orb_, state_]:=Module[
    {binarystate, index},
    index = f*(orb-1)+\[Sigma];
    binarystate = IntegerDigits[#,2,L]&@state;
    If[binarystate[[index,1]]==0,
        binarystate = ReplacePart[binarystate,{index,1}->1];
        Return[FromDigits[#,2]&/@binarystate],
    (*else*)
        Return[0]
    ];
];

Thank you for any help!

$\endgroup$
3
  • 5
    $\begingroup$ Specifying variable types to speed up performance doesn't work/can't be done. But you can probably gain a lot simply by improving the implementation of your functions. For instance, you seem to be only checking whether the bit at position index is set (and setting it if not). This can be done way more quickly using bitwise operations, no need to ever convert the state to a list of digits. Same with your return statement: Why are you converting state to digits and then back again, rather than simply returning the appropriate part of state? Finally, note that Return is not needed here $\endgroup$
    – Lukas Lang
    Sep 16 at 9:10
  • 1
    $\begingroup$ (After the improvements outlined in the previous comment you should also be able to compile the function if you need more performance) $\endgroup$
    – Lukas Lang
    Sep 16 at 9:11
  • $\begingroup$ Thanks! I will stop trying to set the variable types and focus more on reducing the number of functions that I call in each function. Your suggestion was very helpful as I obtained a speed up of a factor 2 / 3. $\endgroup$
    – Matteo
    Sep 16 at 15:22

1 Answer 1

6
$\begingroup$

Here's a version that avoids the explicit conversion to binary digits and uses only bitwise operations:

ClearAll[cdg2]
cdg2[L_, f_, σ_, orb_, state_] := Module[
  {mask, index},
  index = f*(orb - 1) + σ;
  mask = 2^(L - 1);
  MapAt[BitOr[mask, #] &, state, index]
]

state = {6, 21, 5, 29, 13, 28, 26, 8, 28, 2, 9, 16, 26, 19};

Equal @@ Through[{cdg, cdg2}[8, 4, 2, 3, state]]
(* Out: True *)

The timing is improved roughly 4x with this version:

RepeatedTiming[cdg[10, 3, 2, 1, state];, 5]  (* Out: {0.0000242844, Null} *)
RepeatedTiming[cdg2[10, 3, 2, 1, state];, 5] (* Out: {6.975*10^-6, Null}  *)

The above version should be compilable as well (at least MapAt and the bitwise operations are listed in this List of compilable functions).

$\endgroup$
4
  • 2
    $\begingroup$ Building on @MarcoB's solution--Replacing Module with With gives another 2x speed improvement: cdg3[L_, f_, \[Sigma]_, orb_, state_] := With[ {index = f*(orb - 1) + \[Sigma], mask = 2^(L - 1)}, MapAt[BitOr[mask, #] &, state, index]] $\endgroup$ Sep 16 at 16:08
  • 2
    $\begingroup$ Even faster: cdg4[L_, f_, σ_, orb_, state_] := MapAt[BitSet[#, L - 1] &, state, f*(orb - 1) + σ] (i.e. using BitSet and no With at all) $\endgroup$
    – Lukas Lang
    Sep 16 at 17:19
  • 2
    $\begingroup$ Or a compiled version that gives a factor of 5 compared to cdg2: cdg5 = Compile[{{L, _Integer}, {f, _Integer}, {σ, _Integer}, {orb, _Integer}, {state, _Integer, 1}}, MapAt[BitOr[#, 2^(L - 1)] &, state, f*(orb - 1) + σ], CompilationTarget -> "C"] (without BitSet as that is not compilable) $\endgroup$
    – Lukas Lang
    Sep 16 at 17:20
  • 1
    $\begingroup$ Wow! thanks a lot!! I was definitely looking at the wrong thing: the variable types, but there was clearly much more that I could do changing my approach $\endgroup$
    – Matteo
    Sep 16 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.