3 people like it.

Faster Filter

A filter function for arrays that is up to 4x faster and uses less memory. The catch is you need to manage the IndexPool, in case you filter some huge arrays and want the memory back after.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
open System
open System.Threading

type IndexPool private () =
    static let instance = new ThreadLocal<_>(fun () -> ResizeArray<int>(100000))
    static member Instance = instance.Value

type Array with    
  static member inline fastFilter (f: ^T -> bool) (array: ( ^T)[]) = 
    if array = null then invalidArg "array" "Array can not be null."            
    if array.Length = 0 then invalidArg "array" "Array can not be empty."    
    
    let indices = IndexPool.Instance
    indices.Clear()    
    for i = 0 to array.Length-1 do
        if f array.[i] then
            indices.Add(i)
        

    let res = Array.zeroCreate indices.Count
    for i = 0 to res.Length-1 do
        res.[i] <- array.[indices.[i]]
        
    res
namespace System
namespace System.Threading
Multiple items
type IndexPool =
  private new : unit -> IndexPool
  static member Instance : List<int>

Full name: Script.IndexPool

--------------------
private new : unit -> IndexPool
val instance : ThreadLocal<Collections.Generic.List<int>>
Multiple items
type ThreadLocal<'T> =
  new : unit -> ThreadLocal<'T> + 1 overload
  member Dispose : unit -> unit
  member IsValueCreated : bool
  member ToString : unit -> string
  member Value : 'T with get, set

Full name: System.Threading.ThreadLocal<_>

--------------------
ThreadLocal() : unit
ThreadLocal(valueFactory: Func<'T>) : unit
type ResizeArray<'T> = Collections.Generic.List<'T>

Full name: Microsoft.FSharp.Collections.ResizeArray<_>
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
static member IndexPool.Instance : Collections.Generic.List<int>

Full name: Script.IndexPool.Instance
property ThreadLocal.Value: Collections.Generic.List<int>
type Array =
  member Clone : unit -> obj
  member CopyTo : array:Array * index:int -> unit + 1 overload
  member GetEnumerator : unit -> IEnumerator
  member GetLength : dimension:int -> int
  member GetLongLength : dimension:int -> int64
  member GetLowerBound : dimension:int -> int
  member GetUpperBound : dimension:int -> int
  member GetValue : [<ParamArray>] indices:int[] -> obj + 7 overloads
  member Initialize : unit -> unit
  member IsFixedSize : bool
  ...

Full name: System.Array
static member Array.fastFilter : f:('T -> bool) -> array:'T [] -> 'T [] (requires equality)

Full name: Script.fastFilter
val f : ('T -> bool) (requires equality)
type bool = Boolean

Full name: Microsoft.FSharp.Core.bool
Multiple items
val array : 'T [] (requires equality)

--------------------
type 'T array = 'T []

Full name: Microsoft.FSharp.Core.array<_>
val invalidArg : argumentName:string -> message:string -> 'T

Full name: Microsoft.FSharp.Core.Operators.invalidArg
property Array.Length: int
val indices : Collections.Generic.List<int>
type IndexPool =
  private new : unit -> IndexPool
  static member Instance : List<int>

Full name: Script.IndexPool
property IndexPool.Instance: Collections.Generic.List<int>
Collections.Generic.List.Clear() : unit
val i : int
Collections.Generic.List.Add(item: int) : unit
val res : 'T [] (requires equality)
val zeroCreate : count:int -> 'T []

Full name: Microsoft.FSharp.Collections.Array.zeroCreate
property Collections.Generic.List.Count: int
Raw view Test code New version

More information

Link:http://fssnip.net/7Qp
Posted:8 years ago
Author:Jack Mott
Tags: filter