Unpredictable results when allocating graphs with huge number of vertices

[clpippel]

Hello, I carried out a number of tests. See below:

library(igraph)
nvert <- .Machine$integer.max - 1                  # number of vertices's
make_graph      (n=nvert, edges = c() )            # Error in  (out of memory)
make_tree       (n=nvert)                          # Error in  (out of memory)
make_ring       (n=nvert)                          # Error in  (out of memory)
make_star       (n=nvert)                          # crash     <<<<<<<<<<<<<<<
make_empty_graph(n=nvert)                          # Error in  (out of memory)
make_full_citation_graph(n=nvert)                  # crash     <<<<<<<<<<<<<<<

library(igraph)
nvert <- .Machine$integer.max                      # number of vertices's
make_graph      (n=nvert, edges = c() )            # crash
make_tree       (n=nvert)                          # crash
make_ring       (n=nvert)                          # Error in  (out of memory)
make_star       (n=nvert)                          # crash 
make_empty_graph(n=nvert)                          # crash
make_full_citation_graph(n=nvert)                  # crash     <<<<<<<<<<<<<<<

library(igraph)
nvert <- .Machine$double.xmax                       # number of vertices's
make_graph      (n=nvert, edges = c() )            # empty graph, no warning
make_tree       (n=nvert)                          # empty graph, no warning
make_ring       (n=nvert)                          # empty graph, no warning
make_star       (n=nvert)                          # empty graph, no warning
make_empty_graph(n=nvert)                          # empty graph with many vertices's, possible:
                                                   # Error: cannot allocate vector of size 2.1 Gb
make_full_citation_graph(n=nvert)                  # crash     <<<<<<<<<<<<<<<
make_full_citation_graph(n=NA)                     # crash     <<<<<<<<<<<<<<<         

The "out of memory"errors are OK. Crashes are obviously NOK. I am not sure creating empty graphs is OK, when the number of vertices (n) is not equal to zero.

Sysinfo in issue #404

[szhorvat]

A word of caution:

A typical outcome when you request too much memory is that the OS starts swapping (it's what happens on macOS). Worst case: the entire OS will lock up.

---

I can reproduce the make_star crash in C, so the problem may be in the C core with that one.

[clpippel]

Hello, Found this one:

make_full_citation_graph(n=.Machine$integer.max - 1 )  # crash     <<<<<<<<<<<<<<<
make_full_citation_graph(n=NULL)                       # crash     <<<<<<<<<<<<<<<

[szhorvat]

Thanks for reporting the crashes. I would suggest not to spend too much time on testing with .Machine$integer.max. There is no doubt that you will find many issues which in the end come down to integer overflow. I'll make a note of them in the issue tracker of igraph's C core, but these problems would not be prioritized, as they are a bit time consuming to fix, and these problems are not triggered in normal use (only when you purposefully push the system by providing huge integers).

[szhorvat]

We are working on fixing these types of issues, but we are still in the stage of laying the foundation in the C core. Most of these should be fixed in C/igraph 0.10, i.e. the next C core release coming sometime this year.

[szhorvat]

nvert <- .Machine$doubl.xmax # number of vertices's make_graph (n=nvert, edges = c() ) # empty graph, no warning

The empty graph results are due to a typo in the above code. doubl should be double. nvert ended up being NULL here.

If we correct it to nvert <- .Machine$double.xmax, then we get:

> make_tree(.Machine$double.xmax)
Error in make_tree(.Machine$double.xmax) : 
  At core/constructors/regular.c:384 : Number of vertices cannot be negative. Invalid value

This is because of the double value is coerced to an integer, resulting in an integer-type NA:

> as.integer(.Machine$double.xmax)
[1] NA
Warning message:
NAs introduced by coercion to integer range

R represents integer NA as the most negative number, i.e. -2^31. igraph's C core (which is not written specifically for R) does not know that this is supposed to mean a NA and not -2^31.

[clpippel]

Thanks for pointing out the typo and the explanation of the error message regarding the negative number of vertices.

This leaves:

require(igraph) make_full_citation_graph(n=NULL) # crash Igraph version: 1.2.8 <<<<<<<<<<

[szhorvat]

At this moment I am only focusing on igraph's C core (I'm not very much involved with the R interface). In my comment above I was trying to sort out problems that are R-specific from problems which need to be fixed in the C core.

Most of the crashes you pointed out above are now fixed in the development version of C/igraph (to become version 0.10), but this work won't show up in R before R/igraph 2.0 (i.e. it won't be in the next release, 1.3, which will be based on C/igraph 0.9). Also, there are more similar crashes in other graph generator functions, which still need to be fixed. There is a lot more work to be done here, but we'll get there eventually.

[szhorvat]

make_full_citation_graph(n=NULL)

These is a very different type of problem that is in the R interface, not the C core, and it still needs fixing.

[clpippel]

System Info: R version 4.1.2 (2021-11-01) Platform: x86_64-w64-mingw32/x64 (64-bit) Running under: Windows 10 x64 (build 22000) [1] igraph_1.2.11

system.time(make_full_citation_graph(n=44500)) gives ---> Error in make_full_citation_graph(n = 44500) : At vector.pmt:446 : cannot reserve space for vector, Out of memory Timing stopped at: 5.53 56.4 97.34 <---

Or in a second run:

system.time(make_full_citation_graph(n=44500)) gives ---> Error: cannot allocate vector of size 7.4 Gb Timing stopped at: 195.1 364.9 897.6 <---

Or third run: system.time(make_full_citation_graph(n=44500)) gives ---> Error in make_full_citation_graph(n = 44500) : At vector.pmt:446 : cannot reserve space for vector, Out of memory Timing stopped at: 6.17 50.78 92.68 <---

system.time(make_full_citation_graph(n=50000)) gives ---> a crash R exits without warning after a few seconds.

[szhorvat]

Yes, the current version, 1.2.11, still has these problems. The next version, 1.3.0, will also have them, because it will be based on C/igraph 0.9. They will be fixed in 2.0, which will be based on C/igraph 0.10. The fixes I made recently apply to the work-in-progress C/igraph 0.10.

[szhorvat]

This is mostly fixed (as in it shouldn't crash). The fix will be released with 2.0 this month.

It will be fully fixed (as in it will give proper error messages) once all affected functions are moved to auto-generation, or scalar conversion checks are added to manually written code.

Refs: #1051, #1068, #1069

[szhorvat]

I think this should be in a pretty good shape now. Do you want to run a few more tests @clpippel and see what's still broken?

Warning: Doing so may hang your computer as it tries to allocate a very large amount of memory. Testing this may not be worth it. I recommend closing this issue now.

[clpippel]

From which version on of igraph on Windows is this solved? Testing is not a big problem.