Участник:Joparino/Массив переменной длины: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Содержимое удалено Содержимое добавлено
Нет описания правки
Нет описания правки
 
(не показаны 3 промежуточные версии 1 участника)
Строка 1: Строка 1:
В [[Программирование|программировании]] '''массив переменной длины''' ({{lang-en|variable-length array, VLA}}), также называемый '''variable-sized''' или '''runtime-sized''', представляет собой [[Массив (тип данных)|массивом]], длина которого определяется во время выполнения (а не во время компиляции)<ref name=cray>{{cite web |url=http://docs.cray.com/books/004-2179-001/html-004-2179-001/z893434830malz.html |title=Variable Length Arrays |archiveurl=https://web.archive.org/web/20180126153326/http://docs.cray.com/books/004-2179-001/html-004-2179-001/z893434830malz.html |archivedate=2018-01-26 |url-status=dead}}</ref>.
В [[Программирование|программировании]] '''массив переменной длины''' ({{lang-en|variable-length array, VLA, variable-sized array, runtime-sized array}}) представляет собой [[Массив (тип данных)|массив]], длина которого определяется во время выполнения (а не во время компиляции)<ref name=cray>{{cite web |url=http://docs.cray.com/books/004-2179-001/html-004-2179-001/z893434830malz.html |title=Variable Length Arrays |archiveurl=https://web.archive.org/web/20180126153326/http://docs.cray.com/books/004-2179-001/html-004-2179-001/z893434830malz.html |archivedate=2018-01-26 |url-status=dead}}</ref>.
В C массив переменной длины имеет изменяемый тип, который зависит от значения (см. [[Зависимый тип]]).
В C массив переменной длины имеет управляемый переменной тип ({{lang-en|variably modified type}}), который зависит от какого-либо значения (см. [[Зависимый тип]]).


Основная цель массивов переменной длины — это упростить программирование численных алгоритмов.
Основная цель массивов переменной длины — это упростить программирование численных алгоритмов.


Языки программирования, поддерживающие массивы переменной длины: [[Ада (язык программирования)|Ada]], [[Алгол 68|Algol 68]] (для негибких строк), [[APL (язык программирования)|APL]], [[C99]] (хотя впоследствии он был отнесен в [[C11]] к условной функции, для поддержки которой реализации не требуются<ref>{{cite web |url=https://gcc.gnu.org/onlinedocs/gcc/Variable-Length.html |title=Variable Length – Using the GNU Compiler Collection (GCC) |publisher=}}</ref><ref>ISO 9899:2011 Programming Languages – C 6.7.6.2&nbsp;4.</ref>; на некоторых платформах может быть реализован ранее с помощью <code>[[alloca]]()</code> или аналогичных функций) и [[C Sharp|C#]] (как массивы, выделенные стеком в небезопасном режиме), [[Кобол|COBOL]], [[Фортран|Fortran 90]], [[J (язык программирования)|J]], и [[Object Pascal]] (язык, используемый в [[Delphi (среда разработки)|Borland Delphi]] и [[Lazarus]], использующий FPC).
Языки программирования, поддерживающие массивы переменной длины: [[Ада (язык программирования)|Ada]], [[Алгол 68|Algol 68]] (без возможности менять длину строк в двумерных массивах и т. д.), [[APL (язык программирования)|APL]], [[C99]] (хотя впоследствии массив переменной длины стал в [[C11]] необязательной воможностью, поддержка которой не требуется<ref>{{cite web |url=https://gcc.gnu.org/onlinedocs/gcc/Variable-Length.html |title=Variable Length – Using the GNU Compiler Collection (GCC) |publisher=}}</ref><ref>ISO 9899:2011 Programming Languages – C 6.7.6.2&nbsp;4.</ref>; на некоторых платформах это могло быть реализовано ранее с помощью функции <code>[[alloca]]()</code> или аналогичных ей) и [[C Sharp|C#]] (массивы, выделенные на стеке — эта возможность доступна только в небезопасном режиме), [[Кобол|COBOL]], [[Фортран|Fortran 90]], [[J (язык программирования)|J]] и [[Object Pascal]] (язык, используемый в средах [[Delphi (среда разработки)|Borland Delphi]] и [[Lazarus]], компилирующийся с помощью Free Pascal Compiler).


==Память==
==Память==


===Распределение памяти===
===Выделение памяти===


* [[GNU Compiler Collection|GNU C Compiler]] выделяет память для массива переменной длины с автоматическим сроком хранения ({{lang-en|automatic storage duration}}) в стеке<ref>{{cite web |url=https://gcc.gnu.org/onlinedocs/gfortran/Code-Gen-Options.html|title=Code Gen Options - The GNU Fortran Compiler|publisher=}}</ref>. Это более быстрый и простой вариант по сравнению с выделением кучи, и он используется большинством компиляторов.
* [[GNU Compiler Collection|GNU C Compiler]] выделяет память для массива переменной длины с {{нп5|автоматическая переменная|автоматическим сроком хранения|en|Automatic variable|automatic variable}} ({{lang-en|automatic storage duration}}) на {{нп5|Выделение памяти на стеке|стеке|en|Stack-based memory allocation|stack-based memory allocation}}<ref>{{cite web |url=https://gcc.gnu.org/onlinedocs/gfortran/Code-Gen-Options.html|title=Code Gen Options - The GNU Fortran Compiler|publisher=}}</ref>. Это более быстрый и простой вариант по сравнению с выделением в куче, и он используется большинством компиляторов.
* Массив переменной длины также могут быть выделены в куче и внутренне доступны с помощью указателя на этот блок.
* Массивы переменной длины также могут быть выделены в куче, внутри реализации используется указатель на этот блок.


==Реализация==
==Реализация==
Строка 17: Строка 17:
===C99===
===C99===


Следующая функция [[C99]] выделяет массив переменной длины заданного размера, заполняет его значениями с плавающей запятой, а затем передает его другой функции для обработки. Из-за того, что массив объявлен как автоматическая переменная, его время жизни заканчивается, когда возвращается <code>read_and_process()</code>.
Следующая функция на [[C99]] выделяет массив переменной длины заданного размера, заполняет его значениями с плавающей запятой, а затем передаёт его другой функции для обработки. Поскольку массив объявлен как автоматическая переменная, его время жизни заканчивается, когда возвращается <code>read_and_process()</code>.


<syntaxhighlight lang="c">
<syntaxhighlight lang="c">
Строка 31: Строка 31:
</syntaxhighlight>
</syntaxhighlight>


В C99 параметр длины должен предшествовать параметру массива переменной длины при вызовах функций<ref name=cray/>. В C11 определяется макрос {{code|__STDC_NO_VLA__}}, если массив переменной длины не поддерживается<ref>§ 6.10.8.3 of the C11 standard (n1570.pdf)</ref>. GCC имел массив переменно длины в качестве расширения до C99, которое также распространяется на его диалект C++.
В C99 параметр длины должен предшествовать параметру массива переменной длины при вызовах функций<ref name=cray/>. В C11 определяется макрос {{code|__STDC_NO_VLA__}}, если массивы переменной длины не поддерживаются<ref>§ 6.10.8.3 of the C11 standard (n1570.pdf)</ref>. GCC имел массивы переменной длины в качестве расширения до C99, которое также распространяется на его диалект C++.


[[Линус Торвальдс]] в прошлом выражал свое недовольство использованием массива переменной длины для массивов с заранее заданными малыми размерами, поскольку это порождает ассемблерный код более низкого качества<ref>{{cite web |title=LKML: Linus Torvalds: Re: VLA removal (was Re: [RFC 2/2] lustre: use VLA_SAFE) |url=https://lkml.org/lkml/2018/3/7/621 |website=lkml.org}}</ref>. С Linux 4.20 [[Ядро Linux|ядро Linux]] фактически не содержит массивов переменной длины<ref>{{cite web |title=The Linux Kernel Is Now VLA-Free: A Win For Security, Less Overhead & Better For Clang - Phoronix |url=https://www.phoronix.com/scan.php?page=news_item&px=Linux-Kills-The-VLA |website=www.phoronix.com |language=en}}</ref>.
[[Линус Торвальдс]] в прошлом выражал своё недовольство использованием массивов переменной длины малых размеров, поскольку это порождает ассемблерный код более низкого качества<ref>{{cite web |title=LKML: Linus Torvalds: Re: VLA removal (was Re: [RFC 2/2] lustre: use VLA_SAFE) |url=https://lkml.org/lkml/2018/3/7/621 |website=lkml.org}}</ref>. [[ядро Linux|Ядро Linux]] 4.20 фактически не содержит массивов переменной длины<ref>{{cite web |title=The Linux Kernel Is Now VLA-Free: A Win For Security, Less Overhead & Better For Clang - Phoronix |url=https://www.phoronix.com/scan.php?page=news_item&px=Linux-Kills-The-VLA |website=www.phoronix.com |language=en}}</ref>.


Хотя C11 явно не указывает ограничение по размеру для массивов переменной длины, некоторые читатели считают, что он должен иметь тот же максимальный размер, что и все другие объекты, т.е. SIZE_MAX байт<ref>§6.5.3.4 and §7.20.3 of the C11 standard (n1570.pdf)</ref>. Однако это значение следует понимать в более широком контексте ограничений среды и платформы, таких как типичный размер страницы с защитой стека 4&nbsp;КБ, что на много порядков меньше, чем SIZE_MAX.
Хотя C11 явно не указывает ограничение по размеру для массивов переменной длины, некоторые интерпретации полагают, что они должны иметь тот же максимальный размер, что и все другие объекты, т.е. <code>SIZE_MAX</code> байт<ref>§6.5.3.4 and §7.20.3 of the C11 standard (n1570.pdf)</ref>. Однако такую интерпретацию следует понимать в более широком контексте ограничений среды и платформы, таких как типичный размер страницы с защитой стека 4&nbsp;КиБ, что на много порядков меньше, чем <code>SIZE_MAX</code>.


Можно иметь синтаксис, подобный массиву переменной длины, с динамическим хранением с помощью указателя на массив.
Можно воспользоваться синтаксисом, подобным массиву переменной длины, с динамическим хранением с помощью указателя на массив.


<syntaxhighlight lang="c">
<syntaxhighlight lang="c">
Строка 57: Строка 57:
===Ada===
===Ada===


Ниже приведен тот же пример в [[Ада (язык программирования)|Ada]]. Массивы в Ada несут свои границы вместе с ними, поэтому нет необходимости передавать их длину функции Process.
Ниже приведён тот же пример на языке [[Ада (язык программирования)|Ada]]. Массивы содержат свою длину вместе с данными, поэтому нет необходимости передавать их длину функции Process.


<syntaxhighlight lang="Ada">
<syntaxhighlight lang="Ada">
Строка 74: Строка 74:
===Fortran 90===
===Fortran 90===


Эквивалентная функция [[Fortran|Fortran 90]] является
Эквивалентная функция на языке [[Fortran|Fortran 90]].


<syntaxhighlight lang="fortran">
<syntaxhighlight lang="fortran">
Строка 91: Строка 91:
</syntaxhighlight>
</syntaxhighlight>


при использовании функции Fortran 90 проверки интерфейсов процедур во время компиляции; с другой стороны, если функции используют интерфейс вызова до Fortran 90, сначала должны быть объявлены (внешние) функции, а длина массива должна быть явно передана в качестве аргумента (как в C):
Используется возможность Fortran 90 для проверки интерфейсов процедур во время компиляции; с другой стороны, если функции используют интерфейс вызова, который был до Fortran 90, сначала должны быть объявлены (внешние) функции, а длина массива должна быть явно передана в качестве аргумента (как в C):


<syntaxhighlight lang="fortran">
<syntaxhighlight lang="fortran">
Строка 111: Строка 111:
===Cobol===
===Cobol===


Следующий фрагмент [[COBOL]] объявляет массив записей переменной длины <code>DEPT-PERSON</code>, имеющий длину (количество элементов), заданную значением <code>PEOPLE-CNT</code>:
Следующий фрагмент на языке [[COBOL]] объявляет массив записей переменной длины <code>DEPT-PERSON</code>, имеющий длину (количество элементов), заданную значением <code>PEOPLE-CNT</code>:


<syntaxhighlight lang="cobolfree">
<syntaxhighlight lang="cobolfree">
Строка 123: Строка 123:
</syntaxhighlight>
</syntaxhighlight>


Массивы переменной длины в [[COBOL]], в отличие от других языков, упомянутых здесь, безопасен, потому что [[COBOL]] требует указания максимального размера массива — в этом примере <code>DEPT-PERSON</code> не может содержать более 20 элементов, независимо от значения <code>PEOPLE-CNT</code>.
Массивы переменной длины в языке [[COBOL]], в отличие от других языков, упомянутых здесь, безопасен, потому что [[COBOL]] требует указания максимального размера массива — в этом примере <code>DEPT-PERSON</code> не может содержать более 20 элементов, независимо от значения <code>PEOPLE-CNT</code>.


=== C# ===
=== C# ===


Следующий фрагмент [[C Sharp|C#]] объявляет массив целых чисел переменной длины. До версии C# 7.2 требуется указатель на массив, что требует "небезопасного" контекста. Ключевое слово "unsafe" требует, чтобы сборка, содержащая этот код, была помечена как небезопасная.
Следующий фрагмент на языке [[C Sharp|C#]] объявляет массив целых чисел переменной длины. До версии C# 7.2 требовался указатель на массив в «небезопасном» контексте. Ключевое слово <code>unsafe</code> требует, чтобы сборка, содержащая этот код, была помечена как небезопасная.


<syntaxhighlight lang="csharp">
<syntaxhighlight lang="csharp">
Строка 137: Строка 137:
</syntaxhighlight>
</syntaxhighlight>


C# версии 7.2 и более поздних версий позволяют выделять массив без ключевого слова "unsafe" с помощью функции Span<ref>{{cite web |url=https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/operators/stackalloc |title=stackalloc operator (C# reference) |publisher=Microsoft}}</ref>.
C# версии 7.2 и более поздних версий позволяет выделять массив без ключевого слова <code>unsafe</code> с помощью функции Span<ref>{{cite web |url=https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/operators/stackalloc |title=stackalloc operator (C# reference) |publisher=Microsoft}}</ref>.


<syntaxhighlight lang="csharp">
<syntaxhighlight lang="csharp">
Строка 149: Строка 149:
=== Object Pascal ===
=== Object Pascal ===


В этом языке массив переменной длины называется динамическим массивом. Объявление такой переменной аналогично объявлению статического массива, но без указания его размера. Размер массива задается во время его использования.
В этом языке массив переменной длины называется динамическим массивом. Объявление такой переменной аналогично объявлению статического массива, но без указания его размера. Размер массива задаётся во время его использования.


<syntaxhighlight lang="delphi">
<syntaxhighlight lang="delphi">
Строка 161: Строка 161:
</syntaxhighlight>
</syntaxhighlight>


Удаление содержимого динамического массива выполняется путем присвоения ему нулевого размера.
Удаление содержимого динамического массива выполняется путём присвоения ему нулевого размера.


<syntaxhighlight lang="delphi">
<syntaxhighlight lang="delphi">

Текущая версия от 18:23, 15 августа 2022

В программировании массив переменной длины (англ. variable-length array, VLA, variable-sized array, runtime-sized array) представляет собой массив, длина которого определяется во время выполнения (а не во время компиляции)[1]. В C массив переменной длины имеет управляемый переменной тип (англ. variably modified type), который зависит от какого-либо значения (см. Зависимый тип).

Основная цель массивов переменной длины — это упростить программирование численных алгоритмов.

Языки программирования, поддерживающие массивы переменной длины: Ada, Algol 68 (без возможности менять длину строк в двумерных массивах и т. д.), APL, C99 (хотя впоследствии массив переменной длины стал в C11 необязательной воможностью, поддержка которой не требуется[2][3]; на некоторых платформах это могло быть реализовано ранее с помощью функции alloca() или аналогичных ей) и C# (массивы, выделенные на стеке — эта возможность доступна только в небезопасном режиме), COBOL, Fortran 90, J и Object Pascal (язык, используемый в средах Borland Delphi и Lazarus, компилирующийся с помощью Free Pascal Compiler).

Выделение памяти

[править | править код]
  • GNU C Compiler выделяет память для массива переменной длины с автоматическим сроком хранения?! (англ. automatic storage duration) на стеке[англ.][4]. Это более быстрый и простой вариант по сравнению с выделением в куче, и он используется большинством компиляторов.
  • Массивы переменной длины также могут быть выделены в куче, внутри реализации используется указатель на этот блок.

Реализация

[править | править код]

Следующая функция на C99 выделяет массив переменной длины заданного размера, заполняет его значениями с плавающей запятой, а затем передаёт его другой функции для обработки. Поскольку массив объявлен как автоматическая переменная, его время жизни заканчивается, когда возвращается read_and_process().

float read_and_process(int n)
{
    float vals[n];

    for (int i = 0; i < n; ++i)
        vals[i] = read_val();

    return process(n, vals);
}

В C99 параметр длины должен предшествовать параметру массива переменной длины при вызовах функций[1]. В C11 определяется макрос __STDC_NO_VLA__, если массивы переменной длины не поддерживаются[5]. GCC имел массивы переменной длины в качестве расширения до C99, которое также распространяется на его диалект C++.

Линус Торвальдс в прошлом выражал своё недовольство использованием массивов переменной длины малых размеров, поскольку это порождает ассемблерный код более низкого качества[6]. Ядро Linux 4.20 фактически не содержит массивов переменной длины[7].

Хотя C11 явно не указывает ограничение по размеру для массивов переменной длины, некоторые интерпретации полагают, что они должны иметь тот же максимальный размер, что и все другие объекты, т.е. SIZE_MAX байт[8]. Однако такую интерпретацию следует понимать в более широком контексте ограничений среды и платформы, таких как типичный размер страницы с защитой стека 4 КиБ, что на много порядков меньше, чем SIZE_MAX.

Можно воспользоваться синтаксисом, подобным массиву переменной длины, с динамическим хранением с помощью указателя на массив.

float read_and_process(int n)
{
    float (*vals)[n] = malloc(sizeof(float[n]));

    for (int i = 0; i < n; ++i)
        (*vals)[i] = read_val();

    float ret = process(n, *vals);
    
    free(vals);
    
    return ret;
}

Ниже приведён тот же пример на языке Ada. Массивы содержат свою длину вместе с данными, поэтому нет необходимости передавать их длину функции Process.

type Vals_Type is array (Positive range <>) of Float;

function Read_And_Process (N : Integer) return Float is
   Vals : Vals_Type (1 .. N);
begin
   for I in 1 .. N loop
      Vals (I) := Read_Val;
   end loop;
   return Process (Vals);
end Read_And_Process;

Эквивалентная функция на языке Fortran 90.

function read_and_process(n) result(o)
    integer,intent(in)::n
    real::o

    real,dimension(n)::vals
    integer::i

    do i = 1,n
       vals(i) = read_val()
    end do
    o = process(vals)
end function read_and_process

Используется возможность Fortran 90 для проверки интерфейсов процедур во время компиляции; с другой стороны, если функции используют интерфейс вызова, который был до Fortran 90, сначала должны быть объявлены (внешние) функции, а длина массива должна быть явно передана в качестве аргумента (как в C):

function read_and_process(n) result(o)
    integer,intent(in)::n
    real::o

    real,dimension(n)::vals
    real::read_val, process
    integer::i

    do i = 1,n
       vals(i) = read_val()
    end do
    o = process(vals,n)
end function read_and_process

Следующий фрагмент на языке COBOL объявляет массив записей переменной длины DEPT-PERSON, имеющий длину (количество элементов), заданную значением PEOPLE-CNT:

DATA DIVISION.
WORKING-STORAGE SECTION.
01  DEPT-PEOPLE.
    05  PEOPLE-CNT          PIC S9(4) BINARY.
    05  DEPT-PERSON         OCCURS 0 TO 20 TIMES DEPENDING ON PEOPLE-CNT.
        10  PERSON-NAME     PIC X(20).
        10  PERSON-WAGE     PIC S9(7)V99 PACKED-DECIMAL.

Массивы переменной длины в языке COBOL, в отличие от других языков, упомянутых здесь, безопасен, потому что COBOL требует указания максимального размера массива — в этом примере DEPT-PERSON не может содержать более 20 элементов, независимо от значения PEOPLE-CNT.

Следующий фрагмент на языке C# объявляет массив целых чисел переменной длины. До версии C# 7.2 требовался указатель на массив в «небезопасном» контексте. Ключевое слово unsafe требует, чтобы сборка, содержащая этот код, была помечена как небезопасная.

unsafe void DeclareStackBasedArrayUnsafe(int size)
{
    int *pArray = stackalloc int[size];
    pArray[0] = 123;
}

C# версии 7.2 и более поздних версий позволяет выделять массив без ключевого слова unsafe с помощью функции Span[9].

void DeclareStackBasedArraySafe(int size)
{
    Span<int> stackArray = stackalloc int[size];
    stackArray[0] = 123;
}

В этом языке массив переменной длины называется динамическим массивом. Объявление такой переменной аналогично объявлению статического массива, но без указания его размера. Размер массива задаётся во время его использования.

program CreateDynamicArrayOfNumbers(Size: Integer);
var
  NumberArray: array of LongWord;
begin
  SetLength(NumberArray, Size);
  NumberArray[0] := 2020;
end.

Удаление содержимого динамического массива выполняется путём присвоения ему нулевого размера.

...
SetLength(NumberArray, 0);
...
  1. 1 2 Variable Length Arrays. Архивировано из оригинала 26 января 2018 года.
  2. Variable Length – Using the GNU Compiler Collection (GCC).
  3. ISO 9899:2011 Programming Languages – C 6.7.6.2 4.
  4. Code Gen Options - The GNU Fortran Compiler.
  5. § 6.10.8.3 of the C11 standard (n1570.pdf)
  6. LKML: Linus Torvalds: Re: VLA removal (was Re: [RFC 2/2] lustre: use VLA_SAFE). lkml.org.
  7. The Linux Kernel Is Now VLA-Free: A Win For Security, Less Overhead & Better For Clang - Phoronix (англ.). www.phoronix.com.
  8. §6.5.3.4 and §7.20.3 of the C11 standard (n1570.pdf)
  9. stackalloc operator (C# reference). Microsoft.