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.