在 64 位平台開發時是否應盡量避免使用指針？

01-28

32 位平台中，指針類型佔用 4 個位元組，而在 64 位操作系統中，指針類型佔用 8 個位元組，是 32 位平台上的兩倍。在實現數據結構時，指針佔用的兩倍空間對程序內存佔用量的影響尤為明顯。
而一些情況下，指針是可以用數組的下標引用來代替的（靜態 / 動態分配一個數組），這時引用對象的內存佔用可能縮小到 4 個位元組（如果數據範圍長度在 32 位內）或更小，但會使代碼更複雜、不夠清晰。在這種情況下，我們是否應該避免使用指針類型？
如何從時間佔用、空間佔用、編程複雜度等多方面考慮這個問題？
補充一下：
題主是演算法競賽出身，還沒有做過 C / C++ 開發。競賽中數據結構的內存佔用是很關鍵的，而競賽評測使用的 32 位平台沒有這個問題。這裡的問題只針對開發，不針對演算法競賽。

題主用 JavaScript、Python 做過開發，懂得高級語言的內存利用效率是很低的，而如果使用 C++ 這類更靠近底層的語言開發時，是否應盡量提高內存利用效率呢？
針對這一回答 https://www.zhihu.com/question/265348258/answer/292595172，題主自己認為「64 位指針浪費空間」是因為計算機處理的很多數據，其數據量都在 32 位範圍內（用評論里 chunquedong 的話來說，考慮到「現實問題的規模」），因此才有了「用 32 位下標引用代替指針」的想法。
有答主提出不需要考慮這些，那麼，應用程序開發對效率的要求比演算法競賽低嗎？

這個問題在日常開發中通常不需要考慮，但在一些情況下可能需要，例如數據量大、內存受限。

如果要存儲大量同類型數據，是可以考慮用索引（下標）取代指針。索引可選擇少於 64 位的類型。例如，一個樹的數據結構，如果在 64 位架構下用指針實現：

struct Node { Node *parent, *nextSibling, *firstChild; // 8 x 3 = 24 bytes Data data; };

struct Tree { Node* root; };

如果用 32 位索引，實現一個 Memory pool：

const uint32_t nullIndex = 0xFFFFFFFF;


struct Node {

    uint32_t parent, nextSibling, firstChild; // 4 x 3 = 12 bytes

    Data data;

};

struct Tree { Node* nodes; uint32_t root; uint32_t nextFreeNode; };

這樣也避開了用 heap 所需的額外內存開銷（每個分配塊要有 header），也可令節點更緊湊地放置在連續內存中，能提升緩存效率。

除了指針大小，一些相關的類型（如 $exttt{size_t}$ ）也有 32/64 位的問題。以下以 Tencent/rapidjson 作為例子說明。

RapidJSON 的 DOM 存儲 JSON 的樹型結構。每個節點以 $exttt{Value}$ （實際是 $exttt{GenericValue<...>}$ ）存儲，它是一個 variant 類型，可表示 object, array, string, number, true, false, null 這 7 種 JSON 類型。我們不知道使用者要存儲多大的 JSON，例如可能有用戶要解釋一個 10GB 的 JSON。因此，每個 $exttt{Value}$ 的大小對應用中的內存需求可能是至關重要的。

例如當 $exttt{Value}$ 存儲 array JSON 類型時，它使用一個類似 $exttt{std::vector}$ 的概念，需要存儲 $exttt{Value}$ 數組、當前大小、當前容量，以及 variant 的信息。如果大小和容量用 $exttt{Value}$ 的話，64 位架構下的大小就要翻倍了：

$egin{array}{l|c|c} ext{32位下位元組} ext{64位下位元組}\ hline exttt{Value* elements} 4 8 \ exttt{size_t size} 4 8 \ exttt{size_t capacity} 4 8 \ exttt{unsigned flags} 4 4 \ hline 16 28 (32)\ end{array}$

因為 64 位的對齊，加上 padding 就要 32 位元組。

這並不理想，應用在絕大部分情況下一個數組不會有 4G 個或以上的元素。因此，RapidJSON 用自定義的 $exttt{SizeType}$ 類型代替 $exttt{size_t}$ ：

#ifndef RAPIDJSON_NO_SIZETYPEDEFINE /*! def RAPIDJSON_NO_SIZETYPEDEFINE ingroup RAPIDJSON_CONFIG rief User-provided c SizeType definition.


    In order to avoid using 32-bit size types for indexing strings and arrays,

    define this preprocessor symbol and provide the type rapidjson::SizeType

    before including RapidJSON:

    code

    #define RAPIDJSON_NO_SIZETYPEDEFINE

    namespace rapidjson { typedef ::std::size_t SizeType; }

    #include "rapidjson/..."

    endcode
    see rapidjson::SizeType

*/

RAPIDJSON_NAMESPACE_BEGIN

//! Size type (for string lengths, array sizes, etc.)

/*! RapidJSON uses 32-bit array/string indices even on 64-bit platforms,

    instead of using c size_t. Users may override the SizeType by defining

ef RAPIDJSON_NO_SIZETYPEDEFINE. */ typedef unsigned SizeType; RAPIDJSON_NAMESPACE_END #endif

那麼，預設設置下的內存佔用就獲得很大的提升：

$egin{array}{l|c|c} ext{32位下位元組} ext{64位下位元組}\ hline exttt{Value* elements} 4 8 \ color{red}{ exttt{SizeType}} exttt{ size} 4 color{red}{4} \ color{red}{ exttt{SizeType}} exttt{ capacity} 4 color{red}{4} \ exttt{unsigned flags} 4 4 \ hline 16 color{red}{20(24)} \ end{array}$

不過因為內存對齊需求，還是需要 24 個位元組。但那至少也省了 8 個位元組。

還可以給力點嗎？

這問題是關於 64 位平台指針的，事實上，在 x86-64 平台上，只會用到低 48 位地址，有 16 位是不使用的。因此，RapidJSON 後來加入了一個優化，改變 flags 的表示方式，壓縮至 16 位放至於指針的高 16 位：

#define RAPIDJSON_UINT64_C2(high32, low32) ((static_cast&(high32) &<&< 32) | static_cast&(low32))


#if RAPIDJSON_48BITPOINTER_OPTIMIZATION == 1

#define RAPIDJSON_SETPOINTER(type, p, x) (p = reinterpret_cast&((reinterpret_cast&(p)  static_cast&(RAPIDJSON_UINT64_C2(0xFFFF0000, 0x00000000))) | reinterpret_cast&(reinterpret_cast&(x))))

#define RAPIDJSON_GETPOINTER(type, p) (reinterpret_cast&(reinterpret_cast&(p)  static_cast&(RAPIDJSON_UINT64_C2(0x0000FFFF, 0xFFFFFFFF))))

#else

#define RAPIDJSON_SETPOINTER(type, p, x) (p = (x))

#define RAPIDJSON_GETPOINTER(type, p) (p)

#endif
template &

class GenericValue {

    // ...

    struct Flag {

#if RAPIDJSON_48BITPOINTER_OPTIMIZATION

        char payload[sizeof(SizeType) * 2 + 6];     // 2 x SizeType + lower 48-bit pointer

#elif RAPIDJSON_64BIT

        char payload[sizeof(SizeType) * 2 + sizeof(void*) + 6]; // 6 padding bytes

#else

        char payload[sizeof(SizeType) * 2 + sizeof(void*) + 2]; // 2 padding bytes

#endif

        uint16_t flags;

    };
   struct ArrayData {

        SizeType size;

        SizeType capacity;

        GenericValue* elements;

    };  // 12 bytes in 32-bit mode, 16 bytes in 64-bit mode
    union Data {

        String s;

        ShortString ss;

        Number n;

        ObjectData o;

        ArrayData a;

        Flag f;

    };  // 16 bytes in 32-bit mode, 24 bytes in 64-bit mode, 16 bytes in 64-bit with RAPIDJSON_48BITPOINTER_OPTIMIZATION

GenericValue* GetElementsPointer() const { return RAPIDJSON_GETPOINTER(GenericValue, data_.a.elements); } GenericValue* SetElementsPointer(GenericValue* elements) { return RAPIDJSON_SETPOINTER(GenericValue, data_.a.elements, elements); } };

使用了這個優化後，32位和64位架構下同樣只佔 16 位元組。所以在內存方面，配合了特殊的池分配器（只分配不釋放），RapidJSON 可以達到開源世界中的最優水平：

比較多個庫解析 JSON 至 DOM 所佔用的內存（沒成功獲取Qt的內存數據）。 https://github.com/miloyip/nativejson-benchmark

另外，這樣讀寫指針的時候有額外的指令，但對比內存做成的緩存性能問題，通常可以忽略，詳見 x86-64 48-bit pointer optimization for GenericValue by miloyip · Pull Request #546 · Tencent/rapidjson。

回到原來的問題，RapidJSON 是不是可以不用指針，改為用索引呢？是可以的，但壞處是使用者不能選擇其他內存分配器。

最後，一般我們說不要過早優化。但有時候，特別是做公共程序庫給別人使用，我們可能要為最極端的使用情況來做一些優化設計。當然，如果沒有這樣的需求，也不要為軟體增加複雜度，直接用指針好了。

從一個人的回答裡面亂膜的情況看來題主似乎是搞OI的，怪不得會有這種問題，你們去問前人好了，不要把自己乾的事情當成軟體開發，也不要把搞OI獲得的所謂「優化」經驗應用到軟體開發裡面

考慮到64位地址空間實際上只用了48位，的確有16位空間可以用來搞事情

但是我認為當且僅當8位元組的指針真的影響到了你的程序性能或大小的時候，才應該去考慮避免使用指針或者用別的方法來壓縮指針內容

還是那句話，先benchmark證明這裡有瓶頸，再去優化，否則就正常寫

也不要只顧開嘲諷模式。先搬 Donald Knuth 出來鎮樓：

It is absolutely idiotic to have 64-bit pointers when I compile a

program that uses less than 4 gigabytes of RAM. When such pointer
values appear inside a struct, they not only waste half the
memory, they effectively throw away half of the cache.

（Knuth: Recent News）

Knuth 說這話的背景是：他有一天在 Linux x86-64 下面編譯一個程序，發現編譯器竟然沒有支持 ILP32 模式，很驚訝。（註：ILP32 指 sizeof(int) == sizeof(long) == sizeof(void*) == 4）

沒錯，Knuth 既說過「過早優化是萬惡之源」，也說過「強迫我使用 64 位指針是白痴」……

很多人可能會覺得 Knuth 經歷過幾十年前那種計算機資源捉襟見肘的時代，導致對這個問題過於敏感，在現代已經不重要了。確實，絕大部分情況下，這點代價完全可以忽略，但總是有對性能特別敏感的場合對不對，比如高性能計算。內存條好加，CPU cache 不是想加就加的啊，做過高性能計算的同學，對 cache miss 導致幾倍性能差距這種現象應該不陌生。

後來 H. J. Lu 等在 Linux 下實現了 Knuth 想要的 ILP32，命名為 x32 ABI（x32 ABI - Wikipedia https://sites.google.com/site/x32abi/）。有人評測過，在 x86-64 下，x32 ABI 為 SPEC2000 帶來了 13.4% 的效率提升（Performance Characterization of the 64-bit x86 Architecture from Compiler Optimizations』 Perspective）。在高性能計算領域，百分之十幾的提升是逆天級別的，要知道，研究編譯器優化的，如果能把 SPEC2000 提升百分之一，就夠頂會級別了。

當然，如果我們假設高性能計算等極端場景不存在，那麼題主的問題確實沒有什麼意義，嗯。普通的應用程序開發，一般原則是有瓶頸再優化，當然也不是說不可以關注效率，但如果運行效率與開發效率、可讀性、可維護性出現了衝突，優先考慮後者。

工程問題更像那種辦得很傻叉的編程競賽：數據範圍不知道，算分憑心情，題目描述模稜兩可，做到一半出題人突然改題意……

這種情況下，就會有所謂的工程的做法。保持代碼的清晰，簡潔，容易修改就是這種情況下的要求。不是說內存佔用不重要（比如，手機上內存讀寫高就是費電……），但是還有一些更重要的事情。比如說如果傻叉出題人改了題目你不能迅速修改代碼，你就零分了。這可比MLE一兩個點麻煩多了……

就我的經驗來看, 動態調撥二進位資源, 系統API靜態調用改動態調用,及時歸還不再需要的內存等等....... 哪一項節省的內存都比死活不用指針多得多,哪一項的危險性都比死活不用指針低得多.

大兄弟,真的不差那點兒, 別和自己過不去.

先用工具證明你的程序內存佔用瓶頸是在這裡，然後再優化。

當使用64位平台的時候，不僅僅是你的指針變大了，寄存器也會拓展變寬。

同樣地，你的定址範圍也變大了。總的來說，你寫程序應當是更加自由。都有了好幾倍的內存了，為什麼還想著「只佔用像32位平台那樣的內存」呢？有錢也要會花啊。

另外，搞不好可能會「負優化」。

如果你有興趣，可以查一下x64的結構體系。

最後貼一張圖片：

時間佔用：CPU的絕大多數操作都要基於寄存器，對於 64 位 cpu 來說，無論64位還是32位，在運算時都是佔用一個寄存器，都只是一條指令，所以32位在時間佔用方面並沒有優勢。相反，如果為了使用32位而改變你的演算法，可能導致更大的時間複雜度。

空間佔用：通常來說，在數據結構中，指針只佔很小一部分開銷。實際應用中最占內存空間的往往都是貼圖或者數據，而這些數據流的空間佔用與你用不用指針沒有關係。一個方陣的排頭兵是胖子還是瘦子並不影響整個方針的面積。

編程複雜度：顯然，取消指針的編程語言並沒有比C++更難編程，但是這些語言提供了很多其它的更方便的機制，使得無需直接操作指針也能很好的完成任務。而C++本身並沒有這樣的機制，除非專門為此目標設計一個類庫（極有可能有某些組織已經干過這種事），否則你在C++中不用指針會成為一種額外的代價，造成額外的負擔。

因而，總的來說，除了節約少量內存以外，不用 64 位指針並不會帶來明顯優勢，你應當首先評估然後再做出優化選擇，而沒必要在一般場合棄用 64 位指針。

應用開發並非不講效率，而是大多數應用對空間效率的要求並不高。棄用 64 位指針只有空間效率的提升卻沒有時間效率的提升，因而意義不大。

實在忍不住了，還是想來摻一腳……

簡單來說就是，指針佔用的空間成為了瓶頸了嗎？真正的瓶頸是指針帶來的內存開銷，還是一些其他的東西？

32位下4byte，64位下8byte，看起來翻番了是不是很恐怖！

可是你存的數據全都是指針嗎？

考慮到題主說只要做OI，那就不談論一張圖片多耗內存的例子了。

OI里用到一片指針，我能想到的就是鏈表咯（不搞OI）……雙向鏈表每個結點兩個指針，如果保存的值比較小的話，的確可能出現指針成了主要內存開銷的情況。更何況由於struct的alignment，64位指針的存在導致struct至少為8byte對齊，即至少需要24byte。

首先，這種情況下按照孫明琦：在 64 位平台開發時是否應盡量避免使用指針？的方法來利用指針的空餘片段是有道理的。但問題在於，你沒法假定系統給你分配的空間是連續的，即一堆指針可能是零散的，沒有共同的頭部以便你用來壓縮。

更新：x86-64規定了高16位預留。

如果假設內存分配很連續的話，即都為0x0000開頭，那顯而易見，頭部放數據，不過兩個指針結合也就4byte空間，如果要存的信息大於4byte的話……

這個時候，分配一大塊內存（連續的），用下標來模擬指針是有道理的。甚至於確定大小的話，直接拿uint16_t/uint8_t來存下標也是可以的，內存節省MAX。

日常應用中也不乏這種思路（雖然我其實沒看過多少代碼），用數組代替一堆小元素。但是，他們真的是為了節省指針嗎？。

new int32_t[2]，系統真的就只分配了8位元組嗎？malloc需要長度但free不需要長度，很明顯長度信息存在某個地方了。即內存分配是有額外開銷的。既然都是同種元素，元素的大小是固定的，這部分開銷就可以被省去。

自己分配大內存的另一個好處就是，減少這種無用開銷。

其次，CPU和內存的速度矛盾決定了，CPU喜歡連續的、有規律的、局部的訪問。自己分配一大塊內存有助於減少數據的分散，一定程度上減少cache miss，是有利於速度提升的。

而且頻繁的分配釋放，陷入內核也會有開銷（我是真的見識過這種代碼，運算密集里大量小內存分配，優化掉真的有明顯性能提升的那種），自己申請大內存，自己做處理，也有一定意義。

再深入追究一點的話，內存池的概念就要浮出水面了。

換句話說，用數組+下標代替指針，是有意義的，但主要意義可能並不在於節省指針大小的開銷。這種套路在32位平台上也常常存在，難道說32位的指針也是累贅？

此外，如果需要考慮到數組+下標的定址性能問題的話，這個就很難比較了。棧vs堆，聽起來是棧更快吧，但x86既有直接定址也有間接定址啊，差距能有多大？關鍵就在於部分指令的優化罷了吧……關鍵還是在於訪存規律。

回到問題，64位平台開發時需要避免指針嗎？

該怎麼用怎麼用。那些優秀演算法沒用到指針，不一定是為了避免指針開銷，而可能只是優化的副產物而已。

忽略堆尺寸、隨機分配速度、碎片情況和各種zone粗暴地說，當你的指針尺寸膨脹一倍而用戶態地址空間尺寸膨脹超過2^15倍，潛在可用工作集膨脹超過2倍的時候，程序運行的圖景已經超出等比縮放意味上的期望了。

當然如果更大的工作集帶來了更多已經成為瓶頸的碎片，就有點那啥——真姬兒丟人——了。

曾經我們的程序里有一種東西叫q數組實現了這個功能。雖然是Fortran語言但是確實有不少性能優勢。

然而寫的時候只有該程序猿和上帝知道這些是啥，寫完之後只有上帝知道這些是個啥了…… 比起微不足道的性能和空間優勢，還是讓代碼好寫易讀易調試更重要

可以選擇編譯成32位程序用兼容模式……

使用64位的一個重要原因就是為了用超過2GB的內存啊。

你把8Bytes中用不到的內存地址位（現在x86-64是16個bit，但是不一定以後還是這樣），用來存值不就行了，也就是Tagged Pointer，參考這個：

Tagged pointer - Wikipedia

C++這麼難這麼複雜的語言，實現一個功能就動輒幾百K的源碼，那四位元組的指針算啥。

我覺得你可以換其他表達能力更強的語言比如Java和Go。

^_^

你是對內存敏感，還是對效率敏感？

對效率敏感，你考慮過CPU處理非64位對齊的數據的感受嗎？CPU已經那麼多BUG了，你就少讓CPU操點心。

如果你沒法確定 64 位指針有沒有影響到你的程序性能，就拿 x32 ABI 試一遍。要是時間或者空間效率確實提高了不少，而且提高的部分對你有意義，可以考慮優化掉 64 位指針。

分頁阅读： 1 2 3