DOBON.NET DOBON.NETプログラミング掲示板過去ログ

VBScript で LinkedList に値を 10000 回追加するとスタックオーバーフローが発生する

分類:[その他]

2011/01/10(Mon) 18:33:00 編集(投稿者)

OS 名:Microsoft Windows 7 Home Premium 
OS バージョン:6.1.7600 N/A ビルド 7600
システムの種類:X86-based PC
プロセッサ:x64 Family 6 Model 23 Stepping 10 GenuineIntel ~1795 Mhz
物理メモリの合計:3,033 MB

VBScript で LinkedList を実装しています。
LinkedList オブジェクトに値を 10000 回追加すると、処理自体は最後まで行われるのですが、
処理が終わったあとに下記内容の例外ダイアログが表示されます。

[Window Title]
Microsoft R Console Based Script Host

[Main Instruction]
Microsoft R Console Based Script Host は動作を停止しました

問題の署名:
  問題イベント名:    APPCRASH
  アプリケーション名:    cscript.exe
  アプリケーションのバージョン:    5.8.7600.16385
  アプリケーションのタイムスタンプ:    4a5bc670
  障害モジュールの名前:    ntdll.dll
  障害モジュールのバージョン:    6.1.7600.16559
  障害モジュールのタイムスタンプ:    4ba9b21e
  例外コード:    c00000fd
  例外オフセット:    0005204a
  OS バージョン:    6.1.7600.2.0.0.768.3
  ロケール ID:    2057
  追加情報 1:    fcea
  追加情報 2:    fcea164eb3423e7b888024d6cfad1fda
  追加情報 3:    d890
  追加情報 4:    d8903a5f3e1afec7b323857d00e0d88f

google で例外コード c00000fd を検索したところ、スタックオーバーフローのようです。
下記のコードで例外が発生することを確認しました。
LinkedList オブジェクトに値を追加する回数が
   8000 回以下だと、例外は発生しませんでした。
   8888 回だと、例外は発生したりしなかったりでした。
  10000 回以上だと、例外は必ず発生しました。
スタックオーバーフローの例外が発生する原因を教えてください。
みなさまの環境におきまして例外が発生するかだけでもお教えいただけるとありがたいです。
よろしくお願いします。

Option Explicit

call main()

function main()
  call println("start")
  dim list : set list = new LinkedList.init()
  dim i : for i = 1 to 10000
    call list.add(i)
  next
  call println("complete")
end function

function println(value)
  call wscript.stdout.writeline(value)
end function

class LinkedListNode
  dim value
  dim nextNode
  
  function init(value_)
    value = value_
    set init = me
  end function
end class

class LinkedList
  dim head
  dim tail
  
  function init()
    set head = new LinkedListNode.init(empty)
    set tail = head
    set init = me
  end function
      
  function add(value)
    set tail.nextNode = New LinkedListNode.init(value)
    set tail = tail.nextNode
  end function
end class
2011/01/10(Mon) 19:15:07 編集(投稿者)

■No27984に返信(もりおさんの記事)
提示のコードを実行するには、

コマンドプロンプトで
> cscript 〜.vbs
と実行する必要があるのですね。(〜.vbsは保存した先のパス)
【参考情報】http://www.atmarkit.co.jp/fwin2k/operation/wsh03/wsh03_03.html

提示のコードをtest.vbsに保存して、それをダブルクリックして実行しようとしたら「call wscript.stdout.writeline(value)」の行で怒られてしまいました。

この行をコメントにしてダブルクリックで実行すると件のエラーは起きません(wscriptとして実行)
しかし、コマンドプロンプトからcscriptで実行するとおっしゃるエラーが起きることを確認しました。Windows7 Ultimate x64環境です。

DOSプロンプト上でコンソールプログラムとして実行するプログラムに割り当てられるスタックの容量を純粋にオーバーしてるのではないでしょうか?
・デフォルトのスタック容量がいくつなのか?
・その容量を何らかの指定で拡張できるのか?
といったところまでは調べていませんが、その辺を調べてみられてはどうでしょう。
■No27985 に返信(よねKENさんの記事)

> コマンドプロンプトで
>>cscript 〜.vbs
> と実行する必要があるのですね。(〜.vbsは保存した先のパス)

はい、コマンドプロンプトで確認しました。記述しておくべきでした。
補足していただきありがとうございます。

WScript、CScript 両方で実行できるよう WScript.Echo 関数を使っておくべきでした。
function println(value)
  call WScript.Echo(value)
end function

> この行をコメントにしてダブルクリックで実行すると件のエラーは起きません(wscriptとして実行)
> しかし、コマンドプロンプトからcscriptで実行するとおっしゃるエラーが起きることを確認しました。Windows7 Ultimate x64環境です。

WScript を使用するという手がありましたか。
確認してみました。うー、私の環境では WScript でもエラーが発生しました。

よねKENさんの環境でもエラーが発生しましたか。少なくとも私のハード固有のものでは
なさそうですね。Windows7 のエディションにも関わりなく発生するということですか。

> DOSプロンプト上でコンソールプログラムとして実行するプログラムに割り当てられるスタックの容量を純粋にオーバーしてるのではないでしょうか?
> ・デフォルトのスタック容量がいくつなのか?
> ・その容量を何らかの指定で拡張できるのか?

CScript.exe、cmd.exe が使用可能なスタック容量ですか。
google で検索してみましたがこれといったものは見つけられませんでした。引き続き調べて
みます。

次のような無限再帰のコードを実行すると「Microsoft VBScript 実行時エラー: スタック領域
が不足しています」と出力されて処理が中止されました。VBScript のスタック領域とはまた別の
もののようですね。

call recursive()
function recursive()
  call recursive()
end function
■No27984に返信(もりおさんの記事)

VBScript のメモリ管理はよくわかりませんが

> dim list : set list = new LinkedList.init()
こういう記述をすると new LinkedListで作成されたObjectへの
参照がうまく解放されない気がするのですがそういうことはありませんか?
initの中で自分自身を返しているのですが参照カウント自体は上がってしまうのではないかと思うのです。
dim list1
set list1 = new LinkedList
dim list
set list = list1.init()
set list1 = nothing

みたいなことをしなくても良いのでしょうか?
2011/01/12(Wed) 10:09:05 編集(投稿者)

スタックが枯渇というのはスタックアンダーフローを意味するようなので
スタックオーバーフローに修正しました。

■No27987に返信(shuさんの記事)

> initの中で自分自身を返しているのですが参照カウント自体は上がってしまうのではないかと思うのです。

返信ありがとうございます。
参照関連の可能性ですか。

self return のメソッドを除去して、変数に Nothing を代入するようにしてみました。
LinkedListNode の value はエラーと関連がなかったので除去しました。
以下のコードを実行したところ、次のように出力されました。

Microsoft (R) Windows Script Host Version 5.8
Copyright (C) Microsoft Corporation 1996-2001. All rights reserved.

start
LinkedList terminate
  set tail = nothing
  end set tail = nothing
  set head = nothing

LinkedList オブジェクトを破棄するタイミングでエラーダイアログが表示され、処理が中止
されました。LinkedListNode オブジェクト head を破棄する過程において
スタックオーバーフローが発生する模様です。

Microsoft Windows XP [Version 5.1.2600] でも確認してみました。
エラーダイアログが表示されることはありませんでした。しかし、Window 7 と同じように
LinkedList オブジェクトの破棄の途中で処理が中止されました。スタックオーバーフローは
エラーダイアログとして顕現しないものの潜在するみたいです。

Option Explicit

call main()

function main()
  call println("start")
  dim list
  set list = new LinkedList
  dim i
  for i = 1 to 10000
    call list.add()
  next
  set list = nothing
  call println("complete")
end function

function println(value)
  call wscript.echo(value)
end function

class LinkedListNode
  dim nextNode
  
  sub class_terminate()
    set nextNode = nothing
  end sub
end class

class LinkedList
  dim head
  dim tail
  
  sub class_initialize()
    set head = new LinkedListNode
    set tail = head
  end sub
      
  function add()
    dim node
    set node = new LinkedListNode
    set tail.nextNode = node
    set tail = node
    set node = nothing
  end function
    
  sub class_terminate()
    call println("LinkedList terminate")

    call println("  set tail = nothing")
    set tail = nothing
    call println("  end set tail = nothing")

    call println("  set head = nothing")
    set head = nothing
    call println("  end set head = nothing")
    
    call println("end LinkedList terminate")
  end sub
end class
2011/01/11(Tue) 14:01:08 編集(投稿者)

■No27988に返信(もりおさんの記事)

そうするとリスト内容の解放を順次行うメソッドが必要そうですね。

#後ろからと書きましたが修正しました。
2011/01/11(Tue) 22:09:50 編集(投稿者)

■No27989に返信(shuさんの記事)
> そうするとリスト内容の解放を順次行うメソッドが必要そうですね。

連なった LinkedListNode オブジェクトを丸ごと破棄するのがまずいということですか。
LinkedList の class_terminate で LinkedListNode オブジェクトの参照を1つずつ
外すよう下記のように記述してみました。例外は発生しなくなりました。

Option Explicit

call main()

function main()
  call println("start")
  dim list
  set list = new LinkedList
  dim i
  for i = 1 to 10000
    call list.add()
  next
  set list = nothing
  call println("complete")
end function

function println(value)
  call wscript.echo(value)
end function

class LinkedListNode
  dim nextNode
  
  sub class_initialize()
    set nextNode = nothing
  end sub
  
  sub class_terminate()
    set nextNode = nothing
  end sub
end class

class LinkedList
  dim head
  dim tail
  
  sub class_initialize()
    set head = new LinkedListNode
    set tail = head
  end sub
      
  function add()
    set tail.nextNode = new LinkedListNode
    set tail = tail.nextNode
  end function
  
  function clear()
    while not (head is nothing)
      set head = head.nextNode
    wend
    set tail = nothing
  end function
  
  sub class_terminate()
    call clear()
  end sub
end class

tail.nextNode に head を設定して参照が循環するようにした場合も、スタックオーバーフロー
の例外は発生しなくなりました。ただし、オブジェクトの破棄が、オブジェクトの参照が不可能に
なった時点で行われず、スクリプトの終了時に行われるようでした。オブジェクトの参照を1つずつ
外すやり方がよいみたいです。

function add()
  set tail.nextNode = new LinkedListNode
  set tail = tail.nextNode
  set tail.nextNode = head
end function
2011/01/11(Tue) 22:15:08 編集(投稿者)

JScript で同様の処理を実行してみました。スタックオーバーフローの例外は発生しませんでした。
LinkedList オブジェクトに値を 1000000 回追加しても問題ありませんでした。

スタックオーバーフローの例外は CScript.exe の仕様のみに起因するものではなく、
VBScript のリソース管理が関わっているみたいですね。

よねKENさん、shuさん、おかげさまで解決することができました。
VBScript の理解も深まりました。ありがとうございました。

コマンドプロンプトで > cscript list.js を実行しました。
main();

function main() {
  println("start");
  var list = new LinkedList();
  for (var i = 1; i <= 10000; i++) {
    list.add();
  }
  println("complete");
}

function println(value) {
  WScript.Echo(value);
}

function LinkedListNode() {
  this.nextNode;
}

function LinkedList() {
  this.head = new LinkedListNode();
  this.tail = this.head;
  
  this.add = function() {
    this.tail.nextNode = new LinkedListNode();
    this.tail = this.tail.nextNode;
  }
}
解決済み!

DOBON.NET | プログラミング道 | プログラミング掲示板