opengl 行主与列主混淆

7hiiyaii  于 2022-11-04  发布在  其他
关注(0)|答案(9)|浏览(168)

我阅读了很多关于这个的书,读得越多,我就越糊涂。
我的理解是:如果我们有一个数列[1, ..., 9],我们想把它们存储在一个以行为主的矩阵中,我们可以得到:

|1, 2, 3|
|4, 5, 6|
|7, 8, 9|

而列主要(纠正我,如果我错了)是:

|1, 4, 7|
|2, 5, 8|
|3, 6, 9|

其实际上是前一矩阵的转置。
我疑惑:好吧,我看不出有什么区别。如果我们对两个矩阵进行迭代(第一个矩阵按行,第二个矩阵按列),我们将以相同的顺序覆盖相同的值:1, 2, 3, ..., 9
偶数矩阵乘法也是一样的,我们取第一个相邻的元素,然后把它们乘以第二个矩阵列。

|1, 0, 4| 
|5, 2, 7| 
|6, 0, 0|

如果我们把前面的行主矩阵R乘以M,即R x M,我们将得到:

|1*1 + 2*0 + 3*4, 1*5 + 2*2 + 3*7, etc|
|etc.. |
|etc.. |

如果我们将以列为主的矩阵CM相乘,即C x M,取C的列而不是行,我们从R x M得到完全相同的结果
我真的很困惑,如果一切都是一样的,为什么这两项甚至存在?我的意思是,即使在第一个矩阵R中,我可以看到行,并认为他们的列...
我是不是漏掉了什么?行主矩阵和列主矩阵对我的矩阵数学意味着什么?我在线性代数课上经常学到,我们把第一个矩阵的行和第二个矩阵的列相乘,如果第一个矩阵是列主矩阵,这会改变吗?我们现在必须把它的列和第二个矩阵的列相乘,就像我在例子中做的那样,还是完全错了?
如有任何澄清,敬请谅解!

**编辑:**我遇到的另一个主要混淆源是GLM...所以我将鼠标悬停在它的矩阵类型上,然后按F12键查看它是如何实现的,在那里我看到了一个向量数组,因此如果我们有一个3x 3矩阵,我们就有一个3个向量的数组。查看这些向量的类型,我看到了“col_type”,所以我假设这些向量中的每一个都代表一个列,因此我们有一个以列为主的系统,对吗?

我写了这个print函数来比较我的平移矩阵和glm的平移矩阵,我看到glm的平移向量在最后一行,而我的在最后一列...

这只会增加更多的混乱。你可以清楚地看到glmTranslate矩阵中的每个向量代表矩阵中的一行。所以......这意味着矩阵是以行为主的,对吗?那么我的矩阵呢?(我使用了一个浮点数组[16])平移值在最后一列,这是否意味着我的矩阵是以列为主的,而我没有现在它?* 试图阻止头旋转 *

5m1hhzi4

5m1hhzi41#

我认为您将实现细节与用法混淆了。
让我们从一个二维数组或矩阵开始:

| 1  2  3 |
    | 4  5  6 |
    | 7  8  9 |

问题是计算机内存是一个一维的字节数组。为了使我们的讨论更容易,让我们把单个字节分成四个一组,这样我们就有了这样的东西,(每个单个,+-+代表一个字节,四个字节代表一个整数值(假设是32位操作系统):

-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
    |       |       |       |       |       |       |       |       |  
   -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
       \/                   \       /
      one byte               one integer

    low memory    ------>                          high memory

另一种表达方式
因此,问题是如何将一个二维结构(我们的矩阵)Map到这个一维结构(即内存)上,有两种方法。
1.行主要顺序:按照这个顺序,我们首先把第一行放入内存,然后是第二行,依此类推。这样,我们在内存中就有了下面的内容:

-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |   1   |   2   |   3   |   4   |   5   |   6   |   7   |   8   |   9   |
-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

如果我们要访问数组中的$M_{ij}$元素,那么我们可以通过下面的算法来找到数组中的某个元素。如果我们有一个指向数组中第一个元素的指针,比如ptr,并且知道数组的列数,比如nCol,那么我们可以通过下面的算法来找到任意元素:

$M_{ij} = i*nCol + j$

为了了解这是如何工作的,考虑M_{02}(即第一行,第三列--记住C是从零开始的。

$M_{02} = 0*3 + 2 = 2

所以我们访问数组的第三个元素。
1.以列为主的排序:按照这个顺序,我们首先把第一列放入内存,然后是第二列,依此类推。这样,我们在内存中就有了以下内容:

-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |   1   |   4   |   7   |   2   |   5   |   8   |   3   |   6   |   9   |
-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

因此,简短的答案-行为主和列为主的格式描述了二维(或更高)数组如何Map到一维内存数组。
希望这对你有帮助T。

mznpcxlj

mznpcxlj2#

我们先来看看代数;代数学甚至没有“内存布局”之类概念。
从一个代数观点来看,一个M × N真实的矩阵可以作用于一个|R^N向量,并产生一个|R^M向量。
因此,如果您参加考试,并给出一个MxN矩阵和一个|R^N个向量,你可以用简单的运算将它们相乘,得到一个结果--这个结果是对是错,并不取决于你的教授用来检查你的结果的软件是以列为主还是以行为主;它只取决于你是否正确地计算了矩阵的每一行与向量的(单个)列的收缩。
为了产生正确的输出,软件必须用列向量压缩矩阵的每一行,就像你在考试中所做的那样。
因此,对齐列主布局的软件和使用行主布局的软件之间的区别不在于它计算什么,而在于如何
更确切地说,这些布局之间关于主题单行与列向量的收缩的差异只是确定的手段

Where is the next element of the current row?
  • 对于row-major-layout,它是内存中下一个存储桶中的元素
  • 对于column-major-layout,它是距离存储桶M个存储桶的存储桶中的元素。

就是这样。
为了向您展示如何在实践中召唤列/行魔法:
你没有用“c++"标记你的问题,但是因为你提到了”glm“,我假设你可以用C来沿着。
在C
的标准库中,有一个声名狼借的怪物,叫做valarray,除了其他一些棘手的特性外,它还有operator []的重载,其中一个重载可以接受**std::slice**(这本质上是一个非常无聊的东西,只包含三个整数类型的数字)。
然而,这个小切片具有访问行主存储的列方式或行主存储的列方式所需的一切-它有一个开始、一个长度和一个步幅-后者表示我提到的“到下一个桶的距离”。

knpiaxh1

knpiaxh13#

无论您使用什么:只要始终如一!

行主还是列主只是一个约定。没关系。C使用行主,Fortran使用列。两者都可以。使用你的编程语言/环境中的标准。

不匹配的两个将!@#$ stuff up

如果你在一个以列为主的矩阵上使用行为主寻址,你可能会得到错误的元素,读过数组的结尾,等等。

Row major: A(i,j) element is at A[j + i * n_columns];  <---- mixing these up will
Col major: A(i,j) element is at A[i + j * n_rows];     <---- make your code fubar

如果说执行矩阵乘法的代码对于行主值和列主值是相同的,这是不正确的

(Of当然,矩阵乘法的数学运算是相同的。)假设内存中有两个数组:

X = [x1, x2, x3, x4]    Y = [y1, y2, y3, y4]

如果矩阵存储在主列中,则X、Y和X*Y为:

IF COL MAJOR: [x1, x3  *  [y1, y3    =   [x1y1+x3y2, x1y3+x3y4
               x2, x4]     y2, y4]        x2y1+x4y2, x2y3+x4y4]

如果矩阵以行为主存储,则X、Y和X*Y为:

IF ROW MAJOR:  [x1, x2    [y1, y2     = [x1y1+x2y3, x1y2+x2y4;
                x3, x4]    y3, y4]       x3y1+x4y3, x3y2+x4y4];

X*Y in memory if COL major   [x1y1+x3y2, x2y1+x4y2, x1y3+x3y4, x2y3+x4y4]
              if ROW major   [x1y1+x2y3, x1y2+x2y4, x3y1+x4y3, x3y2+x4y4]

这里没有什么深奥的东西。这只是两种不同的约定。就像用英里或公里来度量一样。无论哪种都行,你只是不能在两者之间来回切换而不进行转换!

64jmpszr

64jmpszr4#

你是对的。系统是以行为主还是以列为主的结构存储数据并不重要。它就像一个协议。计算机:“嘿,人类,我就这么收你的阵法,没问题吧。嗯?”不过,说到性能,还是很重要的,考虑一下以下三点。

1.大多数数组是以行为主的顺序访问的。
2.访问内存时,并不是直接从内存中读取。您首先将内存中的一些数据块存储到高速缓存中,然后再将高速缓存中的数据读取到处理器中。
3.如果缓存中不存在所需的数据,则缓存应从内存中重新提取数据

当高速缓存从内存中提取数据时,局部性很重要。也就是说,如果您在内存中稀疏地存储数据,则高速缓存应该更频繁地从内存中提取数据。由于访问内存的速度要慢得多,因此此操作会降低程序的性能(超过100倍!)然后访问缓存。访问内存越少,程序就越快。所以,这个以行为主的阵列更有效,因为访问其数据更可能是本地的。

jjhzyzn0

jjhzyzn05#

好吧,既然“困惑”这个词在标题中是字面上的,我可以理解...困惑的程度。
第一,这个绝对是一个真实的的问题
永远不要屈服于这样的想法,“它是用来,但... PC的现在...”

这里的主要问题包括:-Cache eviction strategy (LRU, FIFO, etc.) as @Y.C.Jung was beginning to touch on -Branch prediction -Pipelining (it's depth, etc) -Actual physical memory layout -Size of memory -Architecture of machine, (ARM, MIPS, Intel, AMD, Motorola, etc.)

这个答案将集中在哈佛架构,冯诺依曼机器,因为它是最适用于目前的PC。
内存层次结构:
https://en.wikipedia.org/wiki/File:ComputerMemoryHierarchy.svgis
是一个成本速度的并列。

对于当今的标准PC系统,这将类似于:SIZE: 500GB HDD > 8GB RAM > L2 Cache > L1 Cache > Registers. SPEED: 500GB HDD < 8GB RAM < L2 Cache < L1 Cache < Registers.

这就引出了时空局部性的概念,一个是指数据是如何组织的(代码、工作集等),另一个是指数据在“内存”中的物理组织位置。
考虑到“大多数”今天的PC机都是小端(英特尔)机器,它们以特定的小端顺序将数据存储到内存中。这与大端有着根本的不同。
https://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Data/endian.html(覆盖它相当... swiftly;))
(For这个例子的简单性,我要“说"的事情发生在单个条目,这是不正确的,整个缓存块通常被访问,并急剧变化我的制造商,更不用说模型)。
现在我们已经知道了,如果,假设你的程序需要1GB of data from your 500GB HDD,加载到8GB of RAM,,然后加载到cache层次结构,最后是registers,程序从最新的缓存行读取第一个条目,以便获得第二个条目(在您的代码中)所需的条目碰巧位于next cache line,中(即下一个ROW而不是column,您将有一个缓存MISS
假设高速缓存已满,因为它很小,在未命中时,根据逐出方案,将逐出一个缓存线,为“确实”具有您需要的下一个数据的缓存线腾出空间。如果此模式重复,则在每次尝试数据检索时,您都将遇到MISS
更糟糕的是,您将收回实际上包含您即将需要的有效数据的缓存行,因此您必须一次又一次地检索它们。
这个术语叫做:thrashing
https://en.wikipedia.org/wiki/Thrashing_(computer_science),并且确实会崩溃一个写得很差/容易出错的系统。(想想windowsBSOD)......
另一方面,如果您正确地布置了数据(即行主要)......您仍然会有未命中!
但这些未命中发生在每次检索结束时,而不是**每次尝试检索时。**这导致系统和程序性能的数量级差异。

非常非常简单的代码片段:


# include<stdio.h>

# define NUM_ROWS 1024

# define NUM_COLS 1024

int COL_MAJOR [NUM_ROWS][NUM_COLS];

int main (void){
        int i=0, j=0;
        for(i; i<NUM_ROWS; i++){
                for(j; j<NUM_COLS; j++){
                        COL_MAJOR[j][i]=(i+j);//NOTE i,j order here!
                }//end inner for
        }//end outer for
return 0;
}//end main

现在,使用以下代码进行编译:gcc -g col_maj.c -o col.o
现在,运行以下命令:time ./col.oreal 0m0.009suser 0m0.003ssys 0m0.004s
现在为ROW主要重复:


# include<stdio.h>

# define NUM_ROWS 1024

# define NUM_COLS 1024

int ROW_MAJOR [NUM_ROWS][NUM_COLS];

int main (void){
        int i=0, j=0;
        for(i; i<NUM_ROWS; i++){
                for(j; j<NUM_COLS; j++){
                        ROW_MAJOR[i][j]=(i+j);//NOTE i,j order here!
                }//end inner for
        }//end outer for
return 0;
}//end main

编译:terminal4$ gcc -g row_maj.c -o row.o运行:time ./row.oreal 0m0.005suser 0m0.001ssys 0m0.003s

现在,如您所见,Row Major的速度明显更快。

**不相信?**如果您想看一个更激烈的例子:使矩阵为1000000 x 1000000,初始化,转置,然后输出到stdout。

(Note,在 *NIX系统上,您将需要设置ulimit unlimited)

我的答案存在问题:-Optimizing compilers, they change a LOT of things! -Type of system -Please point any others out -This system has an Intel i5 processor

q9rjltbz

q9rjltbz6#

这很简单:row-major和column-major来自glUniformMatrix*()的视角。实际上,matrix从未改变,它始终是:

不同的是矩阵类的实现,它决定了16个浮点数如何作为参数存储并传递给glUniformMatrix*()
如果您使用以行为主的矩阵,则4x 4矩阵的内存为:(a11,a12,a13,a14,a21,a22,a23,a24,a31,a32,a33,a34,a41,a42,a43,a44),否则对于主列为:(11、21、31、41、12、22、32、42、13、23、33、43、41、42、43、44)。
因为glsl是以列为主的矩阵,所以它将读取16个浮点数据(b1,b2,b3,b4,b5,b6,b7,b8,b 9,b10,b11,b12,b13,b14,b15,b16),如下所示

由于在以行为主的情况下,a11=b1,a12=b2,a13=b3,a14=b4,a21=b5,a22= b6,......因此,在glsl矩阵中,变为


在以列为主时:a11=b1,a21=b2,a31=b3,a41=b4,a12=b5,a22= b6,......因此,在gls 1矩阵中,被改变为

这和原来的是一样的。所以行大调需要转置而列大调不需要。
希望这能解决你的困惑。

ergxz8rk

ergxz8rk7#

对于C语言,内存几乎是直接访问的,行为主或列为主的顺序在两个方面影响你的程序:1.它影响您的矩阵在内存中的布局2.必须保持的元素访问顺序-以排序循环的形式。
1.在前面的回答中已经解释得很透彻了,所以我将增加2。
eulerworks回答指出,在他的例子中,使用行主矩阵带来了计算上的显著减慢.好吧,他是对的,但结果可以同时逆转.
循环顺序是for(over rows){ for(over columns){ do something over a matrix } }。这意味着双循环将访问一行中的元素,然后移动到下一行。例如,A(0,1)-〉A(0,2)-〉A(0,3)-〉... -〉A(0,N_ROWS)-〉A(1,0)-〉...
在这种情况下,如果A以行为主的格式存储,则缓存未命中将最小,因为元素可能在内存中以线性方式排列。否则,以列为主的格式,内存访问将使用N_ROWS作为步幅进行跳跃。因此,在这种情况下,行为主的速度更快。
现在,我们实际上可以切换循环,这样它将for(over columns){ for(over rows){ do something over a matrix } }。在这种情况下,结果将完全相反。列主计算将更快,因为循环将以线性方式读取列中的元素。
因此,你不妨记住这一点:1.选择以行为主还是以列为主的存储格式取决于您的口味,即使传统的C编程社区似乎更喜欢以行为主的格式。2.虽然您可以自由选择任何您喜欢的格式,但您需要与索引的概念保持一致。3.另外,这一点非常重要,请记住,在编写您自己的算法时,试着对循环进行排序,以便它荣誉您选择的存储格式。4.保持一致。

2w2cym1i

2w2cym1i8#

根据上面的解释,下面是一个演示该概念的代码片段。

//----------------------------------------------------------------------------------------
// A generalized example of row-major, index/coordinate conversion for
// one-/two-dimensional arrays.
// ex: data[i] <-> data[r][c]
//
// Sandboxed at: http://swift.sandbox.bluemix.net/#/repl/5a077c462e4189674bea0810
//
// -eholley
//----------------------------------------------------------------------------------------

// Algorithm

let numberOfRows    = 3
let numberOfColumns = 5
let numberOfIndexes = numberOfRows * numberOfColumns

func index(row: Int, column: Int) -> Int {
    return (row * numberOfColumns) + column
}

func rowColumn(index: Int) -> (row: Int, column: Int) {
    return (index / numberOfColumns, index % numberOfColumns)
}

//----------------------------------------------------------------------------------------

// Testing

let oneDim = [
       0,    1,    2,    3,    4,
       5,    6,    7,    8,    9,
      10,   11,   12,   13,   14,
]

let twoDim = [
    [  0,    1,    2,    3,    4 ],
    [  5,    6,    7,    8,    9 ],
    [ 10,   11,   12,   13,   14 ],
]

for i1 in 0..<numberOfIndexes {
    let v1 = oneDim[i1]
    let rc = rowColumn(index: i1)
    let i2 = index(row: rc.row, column: rc.column)
    let v2 = oneDim[i2]
    let v3 = twoDim[rc.row][rc.column]
    print(i1, v1, i2, v2, v3, rc)
    assert(i1 == i2)
    assert(v1 == v2)
    assert(v2 == v3)
}

/* Output:
0 0 0 0 0 (row: 0, column: 0)
1 1 1 1 1 (row: 0, column: 1)
2 2 2 2 2 (row: 0, column: 2)
3 3 3 3 3 (row: 0, column: 3)
4 4 4 4 4 (row: 0, column: 4)
5 5 5 5 5 (row: 1, column: 0)
6 6 6 6 6 (row: 1, column: 1)
7 7 7 7 7 (row: 1, column: 2)
8 8 8 8 8 (row: 1, column: 3)
9 9 9 9 9 (row: 1, column: 4)
10 10 10 10 10 (row: 2, column: 0)
11 11 11 11 11 (row: 2, column: 1)
12 12 12 12 12 (row: 2, column: 2)
13 13 13 13 13 (row: 2, column: 3)
14 14 14 14 14 (row: 2, column: 4)

* /
yshpjwxd

yshpjwxd9#

现在没有理由使用列优先顺序,在c/c++中有几个库支持它(eigen,armadillo,...)。此外,列主顺序更自然,例如,具有[x,y,z]的图片被逐片地存储在文件中,这是列主顺序。而在二维中,选择更好的顺序可能会令人困惑,在更高维中,很明显,列主排序在许多情况下是唯一的解决方案。
C语言的作者创造了数组的概念,但他们可能没有想到有人会把它当作矩阵来使用。如果我看到数组是如何被用在所有东西都是以fortran和列为主的地方,我会感到震惊。我认为行为主的顺序只是列为主的顺序的替代品,但只是在真正需要的情况下(目前我还不知道)。
奇怪的是,现在还有人用行为主的顺序创建图书馆,这是不必要的浪费精力和时间,我希望有一天一切都是列为主的顺序,所有的混乱都消失了。

相关问题