Kích thước truyền tối ưu của mảng kích thước cố định trong julia

Question

Tôi muốn viết một hàm lấy ma trận làm đầu vào. Đây là một cuộc gọi cấp thấp thường xuyên trong một dự án phức tạp, do đó, làm cho chức năng này càng nhanh càng tốt có tiềm năng tác động hiệu quả nghiêm trọng. Bởi vì tốc độ là rất quan trọng với tôi, tôi đang sử dụng các loại trong FixedSizeArrays vì tôi biết rằng điều này sẽ tiết kiệm được việc sử dụng bộ nhớ. Nhưng tôi thường biết các thuộc tính nhất định của ma trận đầu vào và tôi không chắc chắn rằng tôi đang sử dụng tối ưu điều đó.

Dưới đây là một ví dụ đơn giản. Hãy tưởng tượng rằng chức năng tôi muốn thực hiện những điều sau càng nhanh càng tốt:

using FixedSizeArrays 

function foo(input::Mat) 
# NB: Mat is the FixedSizeArrays matrix type 
    return 2 * input 
end 

Rõ ràng đây là một ví dụ nhỏ, nhưng đó không phải là vấn đề. Vấn đề là tôi biết điều gì đó về kích thước của ma trận input: nó luôn luôn chỉ có hai cột và tôi luôn có thể chỉ định số hàng tại thời gian chạy. Điều này có vẻ như thông tin có thể được chuyển đến trình biên dịch để làm cho mã của tôi nhanh hơn. Tôi có thể vượt qua nó như một đối số xác định kích thước của input bằng cách nào đó? Đây là một ví dụ không hiệu quả, nhưng nên cho bạn biết một số ý tưởng tôi đang cố gắng làm.

function bar(int::N, thismat::Mat{N,2,Float64}) 
    return 2 * thismat 
end 

Có điều gì tương tự mà tôi có thể làm không? Điều này thậm chí sẽ làm việc nếu tôi có thể? Có lẽ FixedSizeArrays đã làm mọi thứ có thể được thực hiện. Cảm ơn bạn đã suy nghĩ!

Answer 1

Mảng cố định kích thước đã được chuyên về kích thước. Các mảng này không thích hợp khi số hàng, N trong trường hợp của bạn, có thể thay đổi. Bất kỳ vấn đề hiệu suất nào bạn nhận thấy có thể do overspecialization.

Hãy để tôi cụ thể hơn một chút.

Trình biên dịch Julia có thể đạt được trừu tượng chi phí bằng không thông qua chuyên môn hóa tích cực trên các loại đối số. Vì vậy, nói chung (có nghĩa là, trong tất cả các trường hợp ngoại trừ một số nơi chuyên môn hóa sẽ quá đắt, hoặc bị vô hiệu hóa rõ ràng), nếu một hàm được gọi với hai chữ ký kiểu khác nhau, thì hai phiên bản của hàm này sẽ được biên dịch.

Vì kích thước của Mat là một phần của loại hình này, điều đó có nghĩa là phiên bản sẽ được biên dịch cho mỗi kích thước có thể có của Mat. Vì vậy, chuyên môn mà bạn tìm kiếm đã hoàn tất.

Chuyên môn, tuy nhiên, không miễn phí. Có hai chi phí liên quan đến nó:

• Lần đầu tiên một hàm được gọi trên một chữ ký cụ thể, bộ nhớ sẽ được cấp phát và trình biên dịch sẽ phải chạy.
• Khi một tham số có loại không thể suy ra được chuyển đến một hàm, có một "loại không ổn định", và công văn động là bắt buộc. Công văn động liên quan đến tra cứu thời gian chạy.

Vì vậy, nếu ma trận của bạn là kích thước (2, N), nơi N thay đổi và không được biết đến tại thời gian biên dịch, chi phí hoạt động của văn động sẽ được phát sinh. Chi phí hiệu năng này có thể bị hạn chế bằng cách sử dụng kỹ thuật rào cản chức năng: chúng tôi chỉ chịu chi phí đó một lần cho mỗi cuộc gọi không ổn định loại, do đó hạn chế số lượng cuộc gọi đó cải thiện hiệu suất.

Nhưng điều gì sẽ làm tăng hiệu suất hơn nữa là tránh hoàn toàn công văn động này.Có thể xây dựng một loại mảng chỉ mã hóa số cột trong loại và có số hàng như một trường lúc chạy. Đó là, có thể vấn đề hiệu suất của bạn là do overspecialization, và bạn cần phải tạo ra các loại của bạn để giảm số lượng chuyên môn.

Tìm số dư phù hợp là trung tâm để ép hiệu suất càng nhiều càng tốt khỏi ứng dụng. Chuyên về kích thước của một mảng là trong thực tế hữu ích khá hiếm - ngay cả mã C và C + +, ví dụ, có xu hướng vượt qua kích thước mảng như tham số thời gian chạy, thay vì chuyên về một kích thước mảng cụ thể. Đây không phải là đắt tiền. Trong nhiều trường hợp không, FixedSizeArrays.jl sẽ không cải thiện hiệu suất, nhưng thay vì làm tổn thương nó. Chắc chắn có những tình huống mà nó sẽ giúp - nhưng bạn có thể không phải là một trong số họ.

---

Trong trường hợp của bạn, cho hiệu suất tối đa, tôi nghi ngờ rằng một loại như thế này sẽ là nhanh nhất:

immutable TwoColumnMatrix{T, BaseType} <: AbstractArray{T, 2} 
    height::Int 
    base::BaseType 
end 

function TwoColumnMatrix(A::Matrix) 
    size(A, 2) == 2 || throw(ArgumentError("must be two columns")) 
    TwoColumnMatrix{eltype(A), typeof(A)}(size(A, 1), A) 
end 

Base.@propagate_inbounds function getindex(M::TwoColumnMatrix, n::Int) 
    M.base[n] 
end 

size(M::TwoColumnMatrix) = (M.height, 2) 

Bạn có thể cần phải xác định phương pháp bổ sung cho hiệu suất tối đa, và như thường lệ, chuẩn mực. Có thể chi phí của trình bao bọc không đáng để trình biên dịch biết về kích thước.