如何用 F# 编写 Duff 的设备?

发布于 2024-12-17 10:05:59 字数 1123 浏览 0 评论 0原文

我正在编写一个性能非常密集的程序,并且一直在使用 C,但有人告诉我函数式编程有多酷,所以我决定用 F# 重写它。

无论如何,我在 F# 中难以复制算法的特定函数是 Duff 的设备。它不是典型的迭代,而是展开循环,以便每次迭代可以复制 8 个字节,而不是仅复制一个。

void copy_memory( char* to, char* from, size_t count ) {
    size_t n = (count+7)/8;
    switch( count%8 ) {
    case 0: do{ *to++ = *from++;
    case 7:     *to++ = *from++;
    case 6:     *to++ = *from++;
    case 5:     *to++ = *from++;
    case 4:     *to++ = *from++;
    case 3:     *to++ = *from++;
    case 2:     *to++ = *from++;
    case 1:     *to++ = *from++;
            }while(--n>0);
    }
}

这利用了 case fallthrough 和跳转到 C 中循环中间的能力,据我所知,不幸的是 F# 似乎缺少这些功能。

我在 MSDN 上阅读了一些内容,并认为 F# 的 match 功能将是我能得到的最接近 C 的 switch 的功能。所以,我开始写这段代码

open System.Reflection
let copyMemory (pTo : Pointer) (pFrom : Pointer) length =
    let n = (length + 7) / 8
    match n % 8 with
    | 0 ->

,然后我不知道该怎么做。它不会让我在这里开始一个循环并在另一个情况下结束它。

F# 中是否有一些东西可以用来执行 case 失败并跳转到循环中间?如果你能为我做到这一点,我想我可以自己解决剩下的事情。

I am writing a very performance intense program and have been using C, but somebody told me how cool functional programming is, so I've decided to rewrite it in F#.

Anyway, the particular function I am having a hard replicating the algorithm in F# is Duff's device. Instead of the typical iteration, it unwinds the loop so it can copy 8 bytes per iteration instead of just one.

void copy_memory( char* to, char* from, size_t count ) {
    size_t n = (count+7)/8;
    switch( count%8 ) {
    case 0: do{ *to++ = *from++;
    case 7:     *to++ = *from++;
    case 6:     *to++ = *from++;
    case 5:     *to++ = *from++;
    case 4:     *to++ = *from++;
    case 3:     *to++ = *from++;
    case 2:     *to++ = *from++;
    case 1:     *to++ = *from++;
            }while(--n>0);
    }
}

This takes advantage of case fallthrough and the ability to jump to the middle of a loop in C, which, as far as I can tell, are unfortunately features that F# seems to be missing.

I read some stuff on MSDN, and figured that F#'s match feature would be the closest I could get to C's switch. So, I started to write this bit of code

open System.Reflection
let copyMemory (pTo : Pointer) (pFrom : Pointer) length =
    let n = (length + 7) / 8
    match n % 8 with
    | 0 ->

and then I couldn't figure out what to do. It wouldn't let me start a loop here and end it in another case.

Is there something in F# that I can use to do case fall-through and jump into the middle of a loop? If you can do that for me, I think I can figure out the rest myself.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

静谧幽蓝 2024-12-24 10:05:59

这是在 F# 中调整内存的惯用方法:-)

#nowarn "9" //stop telling me I'm going to break something
open Microsoft.FSharp.NativeInterop

let inline (~+) ptr = NativePtr.add ptr 1

let rec copyMemory src dest = function
  | 0 -> ()
  | n -> 
    NativePtr.read src |> NativePtr.write dest
    copyMemory +src +dest (n - 1)

但这可能更符合 Duff 的精神

let inline (+>) s d = 
  NativePtr.read !s |> NativePtr.write !d
  s:= NativePtr.add !s 1
  d:= NativePtr.add !d 1

let copyMemory src dst count =
  let n = ref ((count + 7) / 8)
  let s, d = ref src, ref dst
  let 
    rec case_0() = s +> d; case_7()
    and case_7() = s +> d; case_6()
    and case_6() = s +> d; case_5()
    and case_5() = s +> d; case_4()
    and case_4() = s +> d; case_3()
    and case_3() = s +> d; case_2()
    and case_2() = s +> d; case_1()
    and case_1() = s +> d; decr n; if !n > 0 then case_0()
  match count % 8 with
  | 7 -> case_7() | 6 -> case_6()
  | 5 -> case_5() | 4 -> case_4()
  | 3 -> case_3() | 2 -> case_2()
  | 1 -> case_1() | _ -> case_0()

但说真的

System.Buffer.BlockCopy(src, 0, dest, 0, count)

Here's the idiomatic way to fiddle memory in F# :-)

#nowarn "9" //stop telling me I'm going to break something
open Microsoft.FSharp.NativeInterop

let inline (~+) ptr = NativePtr.add ptr 1

let rec copyMemory src dest = function
  | 0 -> ()
  | n -> 
    NativePtr.read src |> NativePtr.write dest
    copyMemory +src +dest (n - 1)

But this is probably more in the spirit of Duff's

let inline (+>) s d = 
  NativePtr.read !s |> NativePtr.write !d
  s:= NativePtr.add !s 1
  d:= NativePtr.add !d 1

let copyMemory src dst count =
  let n = ref ((count + 7) / 8)
  let s, d = ref src, ref dst
  let 
    rec case_0() = s +> d; case_7()
    and case_7() = s +> d; case_6()
    and case_6() = s +> d; case_5()
    and case_5() = s +> d; case_4()
    and case_4() = s +> d; case_3()
    and case_3() = s +> d; case_2()
    and case_2() = s +> d; case_1()
    and case_1() = s +> d; decr n; if !n > 0 then case_0()
  match count % 8 with
  | 7 -> case_7() | 6 -> case_6()
  | 5 -> case_5() | 4 -> case_4()
  | 3 -> case_3() | 2 -> case_2()
  | 1 -> case_1() | _ -> case_0()

But seriously

System.Buffer.BlockCopy(src, 0, dest, 0, count)
深海不蓝 2024-12-24 10:05:59

F# 中没有标签。但是,您可以通过其他方式展开循环。

let copy (dst : nativeptr<byte>) (src : nativeptr<byte>) count =
    let mutable s = src
    let mutable d = dst

    for n in 1 .. count / 8 do
        NativePtr.read s |> NativePtr.write d
        s <- NativePtr.ofNativeInt(NativePtr.toNativeInt s + nativeint 1)
        d <- NativePtr.ofNativeInt(NativePtr.toNativeInt d + nativeint 1)
        NativePtr.read s |> NativePtr.write d
        s <- NativePtr.ofNativeInt(NativePtr.toNativeInt s + nativeint 1)
        d <- NativePtr.ofNativeInt(NativePtr.toNativeInt d + nativeint 1)
        NativePtr.read s |> NativePtr.write d
        s <- NativePtr.ofNativeInt(NativePtr.toNativeInt s + nativeint 1)
        d <- NativePtr.ofNativeInt(NativePtr.toNativeInt d + nativeint 1)
        NativePtr.read s |> NativePtr.write d
        s <- NativePtr.ofNativeInt(NativePtr.toNativeInt s + nativeint 1)
        d <- NativePtr.ofNativeInt(NativePtr.toNativeInt d + nativeint 1)
        NativePtr.read s |> NativePtr.write d
        s <- NativePtr.ofNativeInt(NativePtr.toNativeInt s + nativeint 1)
        d <- NativePtr.ofNativeInt(NativePtr.toNativeInt d + nativeint 1)
        NativePtr.read s |> NativePtr.write d
        s <- NativePtr.ofNativeInt(NativePtr.toNativeInt s + nativeint 1)
        d <- NativePtr.ofNativeInt(NativePtr.toNativeInt d + nativeint 1)
        NativePtr.read s |> NativePtr.write d
        s <- NativePtr.ofNativeInt(NativePtr.toNativeInt s + nativeint 1)
        d <- NativePtr.ofNativeInt(NativePtr.toNativeInt d + nativeint 1)
        NativePtr.read s |> NativePtr.write d
        s <- NativePtr.ofNativeInt(NativePtr.toNativeInt s + nativeint 1)
        d <- NativePtr.ofNativeInt(NativePtr.toNativeInt d + nativeint 1)

    for n in 1 .. count % 8 do
        NativePtr.read s |> NativePtr.write d
        s <- NativePtr.ofNativeInt(NativePtr.toNativeInt s + nativeint 1)
        d <- NativePtr.ofNativeInt(NativePtr.toNativeInt d + nativeint 1)

与此相关的是,NativePtr.add 将在 nativeptr 上调用 sizeof,因此我将其转换为上面的 nativeint。

There are no labels in F#. You can however unroll your loop another way.

let copy (dst : nativeptr<byte>) (src : nativeptr<byte>) count =
    let mutable s = src
    let mutable d = dst

    for n in 1 .. count / 8 do
        NativePtr.read s |> NativePtr.write d
        s <- NativePtr.ofNativeInt(NativePtr.toNativeInt s + nativeint 1)
        d <- NativePtr.ofNativeInt(NativePtr.toNativeInt d + nativeint 1)
        NativePtr.read s |> NativePtr.write d
        s <- NativePtr.ofNativeInt(NativePtr.toNativeInt s + nativeint 1)
        d <- NativePtr.ofNativeInt(NativePtr.toNativeInt d + nativeint 1)
        NativePtr.read s |> NativePtr.write d
        s <- NativePtr.ofNativeInt(NativePtr.toNativeInt s + nativeint 1)
        d <- NativePtr.ofNativeInt(NativePtr.toNativeInt d + nativeint 1)
        NativePtr.read s |> NativePtr.write d
        s <- NativePtr.ofNativeInt(NativePtr.toNativeInt s + nativeint 1)
        d <- NativePtr.ofNativeInt(NativePtr.toNativeInt d + nativeint 1)
        NativePtr.read s |> NativePtr.write d
        s <- NativePtr.ofNativeInt(NativePtr.toNativeInt s + nativeint 1)
        d <- NativePtr.ofNativeInt(NativePtr.toNativeInt d + nativeint 1)
        NativePtr.read s |> NativePtr.write d
        s <- NativePtr.ofNativeInt(NativePtr.toNativeInt s + nativeint 1)
        d <- NativePtr.ofNativeInt(NativePtr.toNativeInt d + nativeint 1)
        NativePtr.read s |> NativePtr.write d
        s <- NativePtr.ofNativeInt(NativePtr.toNativeInt s + nativeint 1)
        d <- NativePtr.ofNativeInt(NativePtr.toNativeInt d + nativeint 1)
        NativePtr.read s |> NativePtr.write d
        s <- NativePtr.ofNativeInt(NativePtr.toNativeInt s + nativeint 1)
        d <- NativePtr.ofNativeInt(NativePtr.toNativeInt d + nativeint 1)

    for n in 1 .. count % 8 do
        NativePtr.read s |> NativePtr.write d
        s <- NativePtr.ofNativeInt(NativePtr.toNativeInt s + nativeint 1)
        d <- NativePtr.ofNativeInt(NativePtr.toNativeInt d + nativeint 1)

On a related note, NativePtr.add will call sizeof on nativeptr so I casted to nativeint above.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文